So one thing which I've felt games have been lacking recently is good storytelling. Since it seems people on this site know their classics, I'd like to hear people's lists of games with great stories or atmospheric storytelling. Sorry if this has been done before, but my search turned up nothing.
My List:
Planescape Torment
Deus Ex
Silent Hill 2
Xenogears
Metal Gear Solid Series
Chrono Cross
Ico
Shadow of the Colossus
Grim Fandango
Killer7
Bioshock
Fallout Series
Half-Life Series
Edit: I've included my tallies for this topic so people don't have to look through the whole topic to see if their game has been mentioned. Some were uncertain so the tally is probably at least slightly incorrect, however it does show the general popular games. I'm surprised the Half-Life series got so high and even more surprised that I haven't played the most popular, which I will do quite soon.
The Witcher - 8
Half-Life Series - 6
Planescape Torment – 5
The Longest Journey – 5
KOTOR series - 4
Deus Ex - 4
Grim Fandango - 4
Fallout Series – 4
Baldur’s Gate series – 4
Indigo Prophecy – 4
System Shock series - 4
Final Fantasy Series – 4
Specific Final Fantasy games mentioned:
Final Fantasy XI
Final Fantasy VI - 2
Final Fantasy VII
Xenogears – 3
Anachronox – 3
Max Payne series – 3
Mass Effect -3
Day of the Tentacle – 3
Monkey Island series - 3
Indiana Jones and the Fate of Atlantis - 3
Full Throttle - 3
Loom - 3
Thief series - 3
Eternal Darkness – 3
Deus Ex: Invisible War - 2
Metal Gear Solid Series - 2
Shadow of the Colossus - 2
Wing Commander series - 2
Bioshock – 2
Marathon - 2
Myth - 2
Neverwinter Nights 2: Mask of the Betrayer - 2
Chrono Trigger - 2
Gabriel Knight: Sins of the father - 2
Sam and Max hit the road – 2
The Dig - 2
Beyond Good and Evil – 2
Outcast – 2
Beneath a Steel Sky - 2
Crusader: No Remorse - 2
Homeworld - 2
No one lives forever - 2
Freelancer - 2
Lands of Lore – 2
Betrayal at Krondor - 2
Myst - 2
Kyrandia - 2
Call of Chuthulu - 2
GTA - 2
Silent Hill 2
Lost Odyssey
Chrono Cross
Ico
Space Quest 1
Space Quest 5
The Adventures of Willy Beamish
Another World
Psychonauts
Portal
Killer7
Amber
Lighthouse
Uncharted: Drake’s Fortune
Cybermage: Darklight Awakening
Interstate ‘76
X-Com
Freespace
Ground Control series
Spellforce series
Okami
Dreamfall
Darwinia
World of Goo
Ultima
Albion
Omikron
Die Hard
Prince of Persia: Sands of Time
Little Big Adventure
Mass Effect
X-wing alliance
G-police
Balde Runner
Vampire: Bloodlines
7th Guest
Noctropolis
Tex Murphy
Freedom Force
Rise of the Dragon
Morrowind
Frontier: Final Encounters
Wastleland
Out of this world
Dungeon Siege 2
Dead Space
Bioforge
Circle of Blood
Command and Conquer
Supreme Commander
Gun
Daggerfall
Halo
Jade Empire
Republic Commando

Other than what you've already listed, the Knights of the Old Republic series and Tron 2.0 both had pretty good stories.
BTW - You listed Deus Ex twice, is one of them supposed to be Invisible War?

My bad, that was a typo and I've never actually played Invisible War anyways.

In that case, add Invisible War to my list. People don't like IW because it was not the same as the first game, but the story was still good.

The Longest Journey
Dreamfall
Xenogears
Final Fantasy games from VI onwards
Lost Odyssey
Half-Life 2
Portal
Shadow of the Colossus
Most LucasArts adventure games from the 90's
Wing Commander games
Mass Effect

I think that Final Fantasy series (lemme say til' X) have got good storytelling, hell the story drives you! Apart from that, my favourite - Planescape: Torment ;]

I agree with most of games listed here, adding two words: The Witcher. The way decision made in the beggining of the way influenced something muuch later was awesome. Oh, and it had best romances ever, at least for me

Text Adventures: Pure Storytelling :)
List: Many of those above my post.
I have issues where good games that have a good come to a sudden end, or where it just takes a turn somewhere into 'Wha?'. Anachronox (sequel please!) is a bit like that, up until the very last bit it's good stuff story/character-wise.
I know there is more like that, but it comes to mind due to the recent play-thru.

Icewind Dale has the best "story telling" of any game ever. Why? because the whole narrative is "some old guy" reading the plot story from a book! You even see the pages turning. And the atmosphere of the candle flickering.. brilliant.
Although Ois may have me beat about text adventures.
edit: that was a joke btw. Serious answer would be Max Payne because of the Noir style. The sequel took it a little too far though IMO.

Uhm.... storytelling insn't necessarily related to "words", imho. I mean, do you remember Out of This World aka Another World aka "The prequel to Flashback and Fade to Black"? It had no words at all but the story it told, while you climbed and ran and fought and jumped, was able to completely transport my imagination years ago. And still today, if I play it, I have the same feelings....

LeftHandedMatt's list is great. It's hard to reply to this without mentioning the adventure games golden ages, so I will add my pick of those available on PC:
Day of the Tentacle
Sam & Max Hit The Road
Monkeyl Island 1 and 2
The Dig
Full Throttle
Space Quest 1 and 5
Beneath a Steel Sky
Gabriel Knight: Sins of the Fathers
The Adventure of Willy Beamish
Indiana Jones and the Fate of Atlantis
Loom
Grim Fandango
Other/Newer:
Beyond Good and Evil
Psychonauts
Outcast (!!!!!!)
Final Fantasy VII
Little Big Adventure 2
Max Payne
As a matter of fact there's one game I've always wanted to play but never have:
Snatcher on SEGA CD. That game needs a remake or an amazing emulator.

Others not yet mentioned:
Baldur's Gate I and II. Not only was the main storyline awesome, many of the side stories were also memorable. I could make a -very- long post on that.
Amber, for the innovative way it melded items in the environment, sounds, phone calls, shadows, books---everything in the whole darn game contributed to telling the story as a whole, and yet it managed to avoid seeming too forced. (Replaying it now after many years so it's fresh on my mind, but it's also why the game stuck in my head for so long.)
Lighthouse, though I wished for a little more filling in of the backstory on the Dark Being.

I agree with almost all listed, particularly Half-Life.
As for others, Freelancer? Uncharted: Drake's Fortune? Homeworld?
They all had great, involving storylines.

I'd exclude adventure games (and maybe RPG's) from the list because their very purpose is to tell a story. What's more interesting are the games from other genres that manage to do it. For example:
No One Lives Forever
Cybermage: Darklight Awakening
System Shock
Crusader: No Remorse
Interstate '76
X-Com
Freespace
etc.

Just listing titles is really uninteresting, people.
I thought Indigo Prophecy (or Fahrenheit in Europe) had a really awesome presentation of interactive storytelling. Interesting take on the adventure gaming genre. The intro really offered an interesting premise that unfortunately devolved into nonsense towards the end. Hopefully upcoming title Heavy Rain will have a better narrative to accompany the interactive presentation.