Red Mages choose Black Mage as their support job for MP and Intelligence. The most popular sub by far, it also offers Elemental Seal, Conserve MP, and certain Black Mage only spells that many find exceedingly useful (Warp, Escape, Sleepga).

Red Mages choose White Mage as their support job for Mind and Healing spells. In addition to Divine Seal, White Mage also offers the -na spell line (Poisona, Silena, etc.) and Curaga. Lastly, White Mage gives Red Mage the ability to utilize his Divine Magic skill with the Banish spells.

Red Mages choose Ninja as their support job for Dual Wield and Utsusemi. This allows them to make incredible use of their enspells (e.g. Enfire, Enthunder, Encetera) and to dual wield stat boosting wands (or for that matter, any weapon that gives bonuses). Also, access to Utsusemi: Ni after level 74 makes them formidable indeed.

Red Mages choose Thief as their support job primarily for farming. Treasure Hunter and Evasion Boost allow a Red Mage to make quick work of worthless prey with little harm to himself, and reap the rewards. At level 50, Flee allows him to do this even faster. In a party, Thief lets a Red Mage use Sneak Attack to add a little extra damage, but many parties will overlook the Red Mage/Thief.

Red Mages choose Ranger as their support job for Wide Scan and Accuracy Bonus. Used primarily for Notorious Monster hunting, or hunting anything that spawns over a wide area, Ranger also offers Red Mage Sharpshot and access to bow weapon skills. In a party, sub Ranger can make a Red Mage an excellent puller, although many parties will prefer a full Ranger or Thief to fill this role.

If you read carefully, you'll notice that I try to stick to the positive aspects of any support job listed, and at the top is the disclaimer to try anything you feel like. When going thru support job sections, any purely negative stuff is removed (e.g. Warrior/Dragoon: Don't do this thin, it the seucksxorrs!1!!11!eleven). Thankfully I haven't seen anything that bad yet ;) I don't see how outlining the positive points of a sub job is detrimental to the Job pages.