I think as a mini-game it would be fun to introduce some sort of small-duration RTS within WoW, using your characters interacting with prominent lore characters etc. Like, say, you have a mission to strike an Orc outpost in Ashenvale, Shandris Feathermoon is under your control, along with your toon, and additional Sentinels. It'd be a stretch though, people would end up complaining about it too. Puzzles and other thinking games as mini-games could also be very interesting. Especially with all the Ancient races in game, having some class or even racial based questline following a combination of scenarios, instances, puzzles, and normal questing could be very engaging.