Personally I think that the core gameplay is as good now as it has been for years. I'd definately keep that the same initially.
I'd keep the Freefall Kombat, lose Klose Kombat and Rage. Bring back Multiple Fatalities and Deathtraps, and KAK, but keep story mode as it is. I like the whole Super Smash Bros. Brawl style of cutscene to fight. Apart from that, a little increase in roster size and a few more Unlockables and I'll be truly sated.