I'd like to see three things:
Epic Mario - we're talking more epic, less kiddy. Let's see something Zelda-like, but for Mario. A huge, long story, side-quests - keep it cartoony if you want (Okami has proven cartoony and epic goes together) or make it a little more modern. And all in a persistent world - not individual worlds accessed from a central hub. I want an epic storyline, twists, side quests.
Or, I'd like to see something with time travel, where Mario either assumes the roles of ancient Marios of time past (i.e., his ascendants), saving ancient Peaches of long lost ages (her ascendants) or he just is himself travelling through time and saving Peach in a variety of ages. We'll see Caveman Mario, Roman Legion Mario, Medieval Mario, Swashbuckling Renaissance Mario - maybe even Futuristic Mario!
Or Mario Brothers: Origins. How did Mario, Luigi, Peach and Bowser get into this never-ending battle? What made Bowser start kidnapping? Why is Peach hot property? What were the Mario Brothers doing and how did they get dragged into it?
What do you think?