Earliest time I can remember being floored by graphics was Mario 64 for the Sega Dreamcast (is funny joke ^^ cause 64 is in the title). The internet was young, so I avoided pictures and mostly stuck to text on GameFaqs. I had never seen a Playstation being played. So, I jumped from a SNES and Genesis to a N64. I had seen better graphics in arcades, but it being in my own house was mind blowing. The environments, and wall jumping in a 3D world enthralled me. Seeing beloved characters (not Peach and Toads, obviously) in bright, colorful 3D melting my little brain.
Bioshock caused me some awe as well, but not it or anything has reached Mario 64 level. Bioshock was just so incredible on high settings! The water looked amazing, walking through that collapsing tunnel at the beginning of the game. Everything was so pretty, even the dirty sinks were a sight. Unfortunately, when I actually had to aim and shoot, my pitiful 8-12 FPS was too crippling to play the game. It looked so much less astounding on Medium, and then even more drab on low (which I would have to play on to get decent frames) that I was too saddened to play it. I didn't pick it up again until a year or two later, when my computer was much better.
The opening cinematic for Super Smash Brothers Melee was astounding to watch on a beautiful Christmas morning.
Crysis: Warhead (I still haven't played more than 5 minutes of Crysis, but have beaten this one and 2) was a delight for the eyes. For the 5 minutes of Crysis I played... well, it was slighty fugly in my opinion. Especially the geometry. Although from a distance, when parachuting in, it was lovley. I think Warhead and Crysis 2 look better :/. This was coming off of beating 2 on Ultra (no DX11 or high res texture pack); and I was playing Crysis on Ultra.
I think I remember Oblivion looking great, but being sad I had nowhere near the computer to play it. I think that's when dual-cores were brand new, and Oblivion listed it as a recommended spec; I think I had a Pentium 3 @800MHz at the time, haha.
The intro sequence to Half Life is still one of my favorite beginnings to a game. So immersive and cool. Even if it does get way too long on subsequent (attempts at) playthroughs.
Dissidia and God of War surprised me on my PSP. I remember being somewhat fascinated watching a friend play Grand Theft Auto on his PSP when it was brand new. Hehe, back when 256MB flash memory was large and expensive.
Going up to the second story of the city of Hengsha in Deus Ex: HR was pretty neat.