Make it have its own character instead of relying on old tropes.

Super Mario Bros. 2 (Doki Doki Panic) was very different to Super Mario Bros. 1. And Super Mario Bros. 3 was again very different from Super Mario Bros. 1 and Super Mario Bros.: the lost levels.

Super Mario World introduced many new things like Yoshi and in Super Mario World 2 you even played as Yoshi! 

The games also frequently changed art styles and they looked good for its time.

So I suggest they do something new. Create a 2.5D Mario platformer with a unique artstyle (Paper Mario artstyle would be cool on an HD console) and gameplay that sets it appart from the rest of the series. Introduce new gameplay mechanics like Yoshi (but NOT Yoshi). Introduce back- and foreground interaction and add a certain "dynamic" to the level. What do I mean with that? Make the levels change while you play them. The new DKC games are a good example of this: in one level you're being chased by a giant octopus, in another by a penguin in a wooden robot suit, in yet another level you're being chased by a horde of tiny spiders, some levels are even falling apart while you traverse them (because of fire, hurricane, unstable icey platforms, etc.), etc.

Make it exciting. Stop rehashing the same old bosses and create unique bosses with many different attack patterns. Make the worlds feel alive. 

Oh, gotcha. So in the post earlier you meant to say "Super Mario Land 2" instead of "World 2" which is Yoshi's Island. Yeah, I'm a Mario fan if you haven't noticed. I also grew up with Gameboy but luckily my cousins always had the newest game consoles so I got to play more. I be the Gamecube would explain your avatar then.

I totally agree with this. Mario needs a new style, new overhaul, new mechanics. And to Nintendo, new always means old which means tried and true Yoshi. It's angering me that NIntendo is sticking on this single style 4 games in! It's beginning to look cheesy to me. I loved that each Mario game changed styles back then. I personally want to see the chubby Mario again.

Nah, I meant Super Mario World 2. I've played it many years later and think its a good game, especially when you consider the time it was released. Only thing that annoys me is that crying Mario! Love the artstyle as well. 

And I was a Metroid fan before I knew it was made by Nintendo! :p 

I also liked Mario Kart, but never paid much attention to who made it! I bought a Wii solely for Metroid Prime 3, but I also bought Super Mario Galaxy (my first 3D Mario) and loved it. Wii is also the era I became a Zelda fan (TP being my first). 

The NSMB games might not be bad per se, but I just call them shovelware because I'm kinda frustrated at all the lost potential. :p 

I hope I didn't offend the games you liked. :) 

I'd be all in for a 2.5D Mario platformer with heavy focus on back- and foreground interaction. DKC: TF is my favorite Wii U game. 

So it looks like the "look" of the games turn you off.  I was really hoping for some insightful gameplay abilities and mechanics that would make you enjoy the games more.  This is the main problem I think developers are up against today...they have to please so many people on so many criteria.  I'm a gameplay first guy, myself...and for that reason I've really enjoyed the updates to the 2D Mario games.  Each iteration has expanded on the options to play the games and has created some very zany moments.  Throwing your friends in lava...priceless!  

Don't get me wrong...I think they could do so much more.  A 2D Mario game in the style of a Metroidvania, for instance, would be my dream come true.  Selectable, stackable abilities!  Could you imagine being able to use fireflowers and iceflowers to make steam taht can be used to fill baloons that you could ride into areas you couldn't get to before?  

I guess that's what I'm really hoping for from Mario Maker...the ability to play within their rules to create gameplay ideas that are definitely outside their traditional box.

Read my post again, I expanded upon it in an edit. :) Hope this makes it more clear for you. 

i wonder what reggie will build....

Pffft, unlike other people on this site I don't get offended by opinions. If you like it, great, if you don't then you don't. People here can't accept that and always want to win arguments. It's sad really. This might be throwing a tangent but if you liked Background-foreground interaction I think Wario Land on Nintendo's virtual boy started that trend. It's actually pretty neat.

A build it your way Mario Pizza courtesy of Pizza Hut.