Might I say, it's full potential was only reached on N64. I loved it as a kid (I still remember hammering the mole for it's bump when I was little), but when I got it on the VC, I didn't get the same thrill as I did before. It's a good game though, don't get me wrong.
Also, I agree with the Super Paper Mario. I have it, my brother beat it, but it's not the kind of game I want. I suck at those kinds of games, I use Paper Mario as an alternative Mario gaming experience, and they just ruined it.
As far as Mario games go, I personally love the one on Super Nintendo (Mario RPG). Nintendo's most genius game of all.