I would probably rewrite everything starting from WOTLK. Remove having DK's available at 58, remove the nonsense about arthas having his humanity, 'there must always be a LK', and goldens retcons of getting rid of Ner'Zhul. Have the LK fight be a world first fight where the champions end up dying and opening up the scourge faction and no deus ex machina with tirion, having him stuck in an ice block. Have a 'rescue Tirion' quest/raid maybe. Once the scourge faction has been unlocked people can choose the necromancer/DK/Dark mage/Acolyte classes to start from. Also having plagued version of the world could be an interesting idea, with some kind of mechanic that generates cool pvp between the three factions? (disabling this on non pvp servers)
Then instead of deathwing in cataclysm, I would introduce another legion expansion, maybe have medivh mysteriously appear and you follow his questline only to find out he was Sargeras and you have accidently ressurected him etc.. I feel like Blizzard could have had alot more to work with story-wise if they removed all the 'good' prevails over 'evil' stuff and stuck to WC3's tone.