I personally have Firion and Maria as Red Mages, while Gus is a white mage with low level black magic(I don't consider this a Red Mage). It is a very difficult thing to do, but I think it is worth the effort, because I can take out most of the monsters with a single sword stroke, and adversly have the same result with magic. I personally love the Red Mage class in general anyways, so I guess it makes me a bit biased. But I think, if you want a challenge, go for a full Red Mage party.