Long post time: tl;dr readers please read the last paragraph (although, if you don't wanna take the time to read this, you suck big ones because there's a lot of thought-provoking material in the following).
I'd make a story and definitive setting for Mario. While I can understand people saying they like their Mario games to be single adventures focused on gameplay, for me, I like to see past all that. When I play a game, I wonder about where I am in Mario's world in relation to locations in past games. I wonder about the inner workings of the kingdom (the block university researching ? and ! blocks' peculiar properties in Superstar Saga was really awesome... just wish it went into more depth) and a ton of other stuff. I wish things in the Mario universe existed for a purpose rather than just existing solely for either providing a backdrop for where you're at or an obstacle for Mario.
I wish Mario had the same story depth and awesome consistency as, say, the Pokemon series. I really enjoy its detailed maps that ties in all the regions together (Kanto, Johto, etc.). I wanna know where World 1-1 from SMB is in relation to, say, Toad Highlands golf course, or whether you can see Isle Delfino from Vista Hill. If you look through a telescope, can you see Star Road? I love large, open world places. I like being able to see things in the distance knowing that I can go to them.
GTA IV and GTA: San Andreas are both good examples of great feeling and use of depth. I also really loved being able to see all the different levels in Sunshine from Delfino Plaza. I loved going to the veeeery top of the enormous palm trees at Pianta Village and looking around the island. Going on top of the ferris wheel at Pinna Park and looking around was also pretty awesome. Now, that is the kind of consistency I like. You could see how all the levels tied in; they weren't just super-isolated places.
Mario's lands, however, are usually always tightly focused and feel claustrophobic. They're typically archipelagian settings (Mario World, Mario RPG, etc.), or "in-close-proximity-to-the-shore" settings (Paper Mario... and.... well, lots of games). Also, that's usually the setting... if we get a large enough map screen in the first place, that is. While isolated areas are kinda not my thing, it'd be cool if there was at least some correlation between all the lands we've seen in Mario games.
I love gaining insight to things in games. Pokemon is another great example. It explains the story behind quite a few things, such as how Pokeballs were first manufactured, the etymology of the word "pokeball" and what Pokemon were called before the invention of the pokeball. I also like how there are legitimate businesses based off Pokemon that produce Pokemon products, such as Silph Co. and Devon Corporation. That, for example, makes me think what businesses are in Mushroom City because there are sure a lot of skyscrapers on that race track in Double Dash. I like how despite having a strange premise which deals with hoards of magical creatures that are caught and trained, etc., the Pokemon world is a normal, functioning, realistic, and coherent world and not just a zany, down-the-rabbit-hole type world.
I'd want to tie every loose end up ever, give shoutouts to characters long forgotten, and make an attempt at illustrating the geography of the Mushroom Kingdom. I'd make an open world Mario game with vast scope and I'd have Mario talk. I'd probably do a billion other cool things, but I've burned myself out talking about all this stuff, so I'll leave it at this.