I had a party of Fighter, Monk, Red Mage and Theif. It worked out well. The Monk is especially good against bosses with a high defense. The Fighter has a great attack and defense. Red Mage is a decent fighter and spellcaster. The Theif came into his own with the class change.

Of course, I was playing in easy mode, so a different party may be better in normal mode.