FF Explorers!

[Mimilu]

Haven't unlocked all the jobs yet but you can basically build your own red mage using the cross-class system on a Freelancer. Unfortunately the skill weight system means you can only equip very basic spells unless you're ok with a smaller ability kit, but you could do it and be functional. With mutations even the most basic spells can be pretty powerful with their short CDs.

You unlock Red Mage by buying Curaga, Firaga, and Quaga.
You can unlock those spells after unlocking 4 star quests and learning the spells before them.
I hear staves are better for Red Mages because of their special skill, Chaincast, makes lowers your cast time and swords don't boost magic damage. :B