The melee side of RDM is actually pretty easy to fix.
#1 give all sword WS, period no room for discussion (a player shouldn't expect to have CDC just to accepted)
#2 put RDM on all the BLU/DNC/NIN/THF gear (we used to be on all this gear, then suddenly SE stuck us on SMN/WHM/BLM gear that even those jobs didn't really want). SE has a history of making really good melee gear, and absolute sh!t mage gear. I'm just happy they didn't screw our Emp Armor up.
Those top two will fix most of the issues.
#3 Fix enspells, all of them. Either modify their formula so that they scale differently post 300 skill, or create a new tier that does scale well. SE could easily double the damage on enspells and it still wouldn't be close to being broken.
*Poof* melee fixed.
Mage is a tad more difficult, mostly due to people not wiling to accept balance issues and wanting to turn RDM into SCH or WHM-1.
Enfeebling, add stat down enfeebles. Monsters already use them, the effect's already exist. I'm talking the icons for "defense down", "attack down", "magic defense down", "evasion down" and so forth, basically everything the GAXE Break line does in spell form. Make sure HNM's are not resistant to these, their not overpowered and would aid immensely to fights.
Enhancing, adjust accession to work with ALL enhancing magic, period, end of story. This will fix lots of stuff, but still we're lacking. I'd suggest making the "Gain-Stat" spells work just like the "Boost" spells, or make them into an aura effect like the VWNM atmacites work. People would be much happier with you on the front line if you were able to boost everyone's STR or DEX.
Healing magic, here is where everyone sh!ts a brick and throws a tantrum. I'd like to break out of the "spam cure" mentality that's been going around. It's unhealthy for a game to be that way. I personally feel that we would get more mileage out of Regen line due to them being enhancing magic and thus work with composure and our various buffs. Change Regen II to 60, add Regen III / IV to RDM, these need to happen (Regen IV is 600Hp over 60s, slightly over 1K HP with our full Emp set). Then add a special RDM only HoT (heal over time) spell with a base duration of 30s (10 ticks) but a potency of 50 that goes up with more enhancing magic, possibly capping out at 80. This would give the RDM the ability to hand out hate free HP and wouldn't step on the WHM's cure toes. Regen is a HP prevention method more then a HP recovery method, tank gets hit for 200, recovers 30 (regen IV) and so forth.