I'm an old school adventure game fan (King's Quest, etc). I love the Zelda series, Link to the Past (SNES) being my favorite. I'm not too keen on the new school 3D games. Having said this, Eternal Darkness: Sanity's Requiem is one of my all time favorites, it's on GameCube.
If you have an Xbox, give Fatal Frame 2: Crimson Butterfly a try, different but really good game.
Should be able to find either of these games used and cheap.
If you love Zelda, I second Beyond Good and Evil.
Almost forgot, an awesome, I mean VERY awesome and addicting adventure game, Sphinx and the Cursed Mummy. It's on GC, Xbox, and PS2.
Sphinx you get to play as two different characters with different abilities. One of the cool things about Eternal Darkness is playing as several characters...