Super Mario World, for SNES. Mario 64 was innovative, and to me, defined the new era at the time. However, SMW was deeper for its time, with an absolute myriad of levels and entertainment to be had.
Mario Kart nearly got a vote, but like someone said, isn't true "Mario". Personally, I think Mario Kart 64 was a better game - 4 player battle mode was the shiznit. I probably spent more hours on the original though.