Well, storytelling wise, i'm glad somebody mentioned the No One Lives Forever series. The two episodes are awesome and i often dream of a n°3 with high-end graphics but the same storytelling...
I love the Witcher, the Kyrandia series, the Indiana Jones series, The Baldur universe (but not NWN 2). Final Fantasy VI was a big shock for me storytelling wise, but i don't know for the others, never played them. I quite loved the Die Hard game.

Little Big Adventure/Relentless has a wonderfully told story.
Pretty simply really, but very nicely done, kinda going from dark to charming in places.
Great game too.
A part from that the only examples of great storytelling are games not suitable for this site.
Prince of Persia: Sands Of Time = well praised, superb storytelling.
Eternal Darkness (gamecube) = Curious structure, a multiple-viewpoint horror story set over thousands of years, very well done
---
I am quite strict in my requirements mind.
Beyond Good and Evil, I thought had a wonderfull atmosphere, design, music and gameplay...but I personaly felt the story wasnt that great. At the end of the day it was just Good and Evil, the title implied more shades of grey.
I suspect the story might be intended to be two parts and then cut back, mind you.

Heh, it's an easy mistake to make. It's not always the first titles you think of when 'storytelling' comes up (usually it's a whole bunch of classic RPG's), but yeah, it surely is fabulous. :)
Quite good, but what brings it down is that it feels more like a game/movie rather than a game/book - so it doesn't make my list here, I'm afraid. Still a great game, though.
Oh, man! As I was composing my neat little list, I was thinking to myself: "I can't forget Eternal Darkness!" but guess what I did? That's right, I forgot to add it. Like you say, it's a great storytelling-based game. The atmosphere is amazing, and the progression with all the different time-periods in mind, is great!

Back in the day Homeworld made great impression on me. I'm not sure though if it was the story telling or general mood setting, the epic scope of the story.
I'm currently plying Wither and think its the best RPG I've played, love both the story and game mechanics.
From the sci-fi games, most memorable stories had G-Police, Half-Life, Deus Ex, X-wing Alliance...

Excellent stories:
Dues Ex 1 & 2
Planescape: Torment
Blade Runner
Fallout series
Legend of Kyrindia old-school stuff (anyone?) :)
Half-life series somewhat
Vampire: Bloodlines
Chuthulu: Dark Mythos or whatever it's called
And not PC but very worthy of good story RPG's:
Anything Final Fantasy
Chrono-Trigger
Square-Enix etc.

Games With a Good Story : Anything from lucasgames until circa 2002, Ex:
Day of the Tentacle
Monkeyl Island 1 and 2
Full Throttle
Loom
Grim Fandango
From Sierra:
All space Quests
Gabriel Knight: Sins of the Fathers
Others:
Beneath a Steel Sky
7Th Guest
Noctropolis
Call of chtulhu games (Shadow of the comet and Prisoner of Ice)
Tex Murphy Games
Most Recent:
Max Payne
Farenheit or whatever you want to call it.

I have a question for those who liked KOTOR. I've had the major plot twist spoiled for me, is the game still worth it for the story (I have it, just never had the will to finish it)?

For side-quests, for another, small stories along the way, for ending, for everything that leads to that twist? Of cours it IS worth it!

It is unfortunate that one of the best surprises in video game storytelling was stolen from you. However, if you've played the game you know that it is still a very good game to play and therefore worth finishing. Also, there are a couple of paths that you can choose that have made many people I know replay the game anyway, obviously knowing the plot twist.
If you're willing to take any advice from a complete stranger who does not yet deserve your trust, I would say play on and enjoy KOTOR is still a great game!

I am surprised so few people mentionned "The witcher". The story is very good, not absolutely the best but still very good.

Totally agree :) I recommend playing thought this game at least two times, as good and as dark Jedi. Darks offensive powers are just awesome. and both endings are a must see.

I'd have to add Freelancer to the other games already mentioned. It was sadly a short story, but very good nonetheless. Then there's the Freedom Force series especially the first one where Manbot sacrifices himself and never gets to be with Alchemiss.
My other personal favs with great storytelling are KotOR series and Wing Commander series.

This is a good point. The Witcher also had the single most affecting moment I've ever experienced in a game.
SPOILERS BEGIN HERE
After you kill the Grand Master, you take his stuff. One of the things he's carrying is a whatever-it-was amulet. It's just like the one you gave to Alvin, only older.
And then it hit me. Shortly after I gave Alvin the amulet, he vanished. He could be anywhere in space or time, Triss said. Alvin kept having horrible dreams, just like the Grand Master did. And the Grand Master's opinions were strikingly similar to what I'd told Alvin.
...
The Grand Master... was Alvin? That couldn't be.
Or could it?
SPOILERS END HERE
Oh shit. I caused that.
And the crazy thing is that it happens no matter what you do. No matter what I did, things would've turned out essentially the same there. Yet I still felt responsible.
I've never had that happen before. I don't think it'll happen again. But I do hope it does.

The Witcher, Morrowind, Mass Effect, Final Fantasy, GTA, Halflife, the list goes on and on