Remember the 3D renders of Mario that Nintendo used (and still uses) for the concept art in SM64 and SMS? The visuals should be like that in the next 3-D Mario game. Realistic to a degree, but with a soft, cartoony feeling to it, all very smooth, polished, and easy on the eyes --- just the right balance of realism and cartooniness. To name a few effects that I think should be included, I'd like to see the water and heat effects from SMS kept, as well as the morphing, cel-shaded clouds in the sky from Wind Waker. All in all such an approach would combine to make a very visually pleasing game.
As for the game, I think each world should consist of a huge, wide open central region with plenty of nooks and crannies to explore and things to do, but with paths branching out from around it, paths that seamlessly lead into more linear obstacle courses and such (like SMS's Warp Stages) where the real meat of the game would be.
For instance, imagine Mario hopping out of a Warp Pipe and landing knee-deep in snow on a windswept valley swirling with ice and snow. You flip to first person perspective and examine the area. Behind you is a skyscraping mountain rising straight up from the valley floor, and you can see hundreds of slippery ledges that you could clamber up to reach the distant top. You run, hop, skip, jump, and flip your way to the mountain and begin the perilous journey up, warding off assaults from airborne enemies as you tread carefully across icy ledges and skillfully jump to and fro. Then, when you finally reach the summit, from which you see the entire valley, with its snowy forests, sparkling caves, and misty lakes, you are faced with very linear obstacle course filled with all sorts of insane platforming challenges, just like the Warp Zones in SMS. And at the end is your Star.
In my opinion, it's the best of both worlds, and should suit Mario fine, with the right curve of difficulty and implementation. And yes, the game should be seasoned well with TONS of nostalgic touches, with everything from the Super Mushroom and Fire Flower to the Tanooki Suit and Hammer Bros. Suit, from the Koopa Kids to Wario and Wart, from worlds of fire and ice to climatic battles aboard airships, everything, all brought to new life on next generation hardware.
Now THAT would be quite something!