it was sorta the same shock and awe i felt when i first saw Super Mario World on the SNES walking around the mall, then games like Driver and Driver 2 on playstation, the player animation on the main menu of Madden 2001 on PS2, then GTA 3, Gears and Halo 3 ect...
i guess i was like 12-13 walkin around in a Toys R Us december of 96, walked passed a playstation kiosk with madden which looked dope as hell and was gonna be my choice for christmas present, was about to ask mom for that, then she came and told me about this "new game system over here" and there was like 10 full kiosks with mario 64 set up and a bunch of parents all standing around, i dont think anyone else was playing it.
i remember seeing the controller and figuring out how to hold it in like 2 seconds, tested out the controls, it was that underground level with the pillars and water, after playin for like 5-10 minutes i was like forget playstation, i want this!
but i seem to remember my first game being Shadows of the Empire, not Mario, i think maybe they were sold out cause we were shopping in december and it had just came out or maybe it came bundled idk, that game was dope as hell too tho.
as for Mario 64 itself, it took me like maybe 2 years or something to actually get all the stars and finish the game, cause i had gotten stuck on one of the later sections and stopped playing it for a while.