The two Cie'th and the Adamantoise are more difficult than Venjingetrix. Venjingetrix has just 15 million Hit Points. For the two Cie'th you should equip weapons with the Lucky Stagger ability. And of course Fang with her ultimate weapon, the super move "Highwind" and the Genji Glove plus your strength + and defense - spells are just POWERFUL. With these things you can easily beat the Adamantoise for example for your gil and the Traphezodron item.
@Wonder: No, the missions do not have anything to do with the main story itself.