I've played a few of the old Infocom games; the best were Wishbringer, a very approachable game; Enchanter, where you cast magic spells; Infidel, where you're a treasure hunter exploring an Egyptian pyramid; and The Lurking Horror (my PC speaker is screaming at me). Too many of them, though, are aimed at the Mensa crowd - even with a walkthrough, I have no idea what I'm doing or why in Zork III or Spellbreaker.
I much prefer the later graphic adventure games, the ones with sound and pictures and animation, where you either steer the character around with the keyboard and try to type furiously before you're eaten by an ogre, or point and click at things until something happens. The LucasArts games are probably better known these days, but I'm a Sierra fan; they have more emphasis on adventure, they have better stories, and they're often more immersive. People complain that you can die, but that just adds to the fun. Quest for Glory, King's Quest, Space Quest, The Dagger of Amon-Ra, and Conquests of Camelot are all great.
I don't rate Monkey Island 2, Day of the Tentacle or Grim Fandango very highly. Tentacle has some clever puzzles involving time travel (the wine bottle), but comes across as a series of baroque logic puzzles rather than a story in its own right; while the first version of Fandango is unplayable, and I got to the wheel puzzle in the remastered version before figuring I had better things to do with my life. I really liked the Telltale Sam and Max series, though, especially the episode set on the Orient Express and in a pyramid, where you're jumping between film reels.
The Last Express (Orient Express again, this time in in 1914), the Broken Sword series and Discworld Noir are also brilliant games. If you can track down a copy, get hold of The Gene Machine , a very funny Jules Verne spoof.
[MENTION=7280]Lark[/MENTION]: Fighting Fantasy rocked! Back in primary school, everyone played these; I got a job lot a few years back, and have been playing through them when I get the chance. I generally prefer the earlier ones - Citadel of Chaos, City of Thieves, Deathtrap Dungeon - although the real stand-outs are Creature of Havoc, in which you play the monster, and don't get free will until well into the game; House of Hell, a Hammer Horror pastiche; and the Sorcery! series, which has cool settings (Kharé, Cityport of Traps; the Archmage's castle) and a really clever time travel spell in the fourth book. The later ones are often formulaic or convoluted, or bizarre (Sky Lord?).