This might not be the biggest improvement of all, but I would love to see DoTs in their kit! I feel like RDM is really missing them (the other casters have DoTs so why not?), and that would add some more reliable damage on top of everything else to help the class perform better.
As to how they would do it, maybe change VerThunder and VerAero to DoTs (that produce one respective mana per tick, maybe?) and give us VerBlizzard and VerAqua to replace the two aforementionned spells.