THe obvious successer to the Red Mage is the Sage, with is abitity to use all magics. However, as has been said, that leaves you with only one physical fighter, so mabye a Dark Kight or a Knight, both of which can fight and use some Magic.

Personally i changed my Red mage to a Black Mage, and he became my Black Magic user. I figure that you don't really need two White magic users, so in your party you should just change your Red Mage to a Dark Knight, shove in a couple of Black magic Spells, and your ready to go. Or, simply abandon the magic altogether, and make him a Dragoon/Ninja.

Another idea, what about a Scholer? He can use Black and White magic, has fairly powerful attacking (if your emey has a weakness, his elemental books are wicked), plus he has a dead useful skill of doubling effectivness of items, so you can make idtems such as Antartic Wind very powerful, as well as becoming a secondary healer by healing with High Potions for 1000hp each. What do you guys think?