I think it was...
one of the Bugs Bunny Crazy Castles, not sure exactly which one. Gosh, I remember that I randomly knew a code (I think I just randomly got it by typing something random in it), and like getting way further in the game. Without it, I only got to like 10 levels before dying. Got to remember I was three.
But my first Mario game has to be Super Mario 64.
EDIT - It was Bugs Bunny Crazy Castles 3. I just youtubed it and I instantly remembered the first level. To be honest, I sucked at that game; always hated how Daffy Duck would make you lose a life if you touch him.