The Half-Life series were great for making the most of the interactive medium.

I read some of the choose your own adventure books and none of the ones I read were that good at keeping track all the various variables that were needed for Planescape: Torment. You also had to keep track of all the inventory and stats yourself with pencil and paper which can be a bit jarring if the books tried to include more variables. Also, I can't think of any chose your own adventure book that had as good of writing as Planescape: Torment. Also, like I said, the music and graphics add quite a bit to the experience I think as well. Besides the Curst prison and an optional dungeon to get a cool party member I didn't really get that bored with Planescape: Torment combat wise. I'm not sure if combat truly hurt the game that much. Yet, I'm not that huge of a fan of D and D mechanics in video games, I tried Baldur's Gate 2 but always got bored during it...

Ah, mostly japanese game designs:

Silent Hill (as a series) - but particularly 2. Most of the storyline on its own is well conceived, but it has that lingering afterthought you never would have thought before happen.

Metal Gear Solid (also as a series) - I'm one of those "it's so meta and postmodern" types.

ICO/SotC - dialogue itself is meaningless, only contextual. How do you tell an experience? You can't. You experience it.

Myst - like the whole game, the story itself is a puzzle. You just don't know how many pieces it has. Not even when it's done. Because it's not finished.

Walls of text and picking answers is also a way of playing a game, in the same way as walking trough a corridor and shooting things is.

It's true that the combat is not the game's strength and that PS:T requires you to read a lot and is therefor atypical for a modern interactive computer game, but funnily enough I can't think of any other RPG that has ever drawn me in as much as PS:T did, so the story-telling can't be all that bad. And no choose-your-own-adventure novel did ever come with such a great soundtrack and atmosphere before. ;)

Since you are giving us the example of FEAR 3, I want to give a FPS example of oustanding storytelling :

S.T.A.L.K.E.R : Shadow of Chernobyl, and S.T.A.L.K.E.R Call of Prypiat.

Call of Prypiat has among the best constructed quests I have ever since in any games, including RPGs...

Bioshock 2. I know a lot of people immediately think of the first as having an awesome story, and it does, but I think that Bioshock 2 had a better one. I liked the whole premise of the story: you're a Big Daddy, and you're Little Sister needs you to rescue her. I also liked the way you choices throughout the game determined (SLIGHT SPOILER) how Eleanor reacted to her mother at the end of the game. I thought it was touching (SPOILER END).

Cryostasis. This one is a bit harder to explain. The story itself is fairly simple once the game plays out, but the way it is presented and the way it requires a little thinking to truly understand what happened really made the story stick out. I also liked the atmosphere and the philosophical aspect of the game.

Final Fantasy XIII. I know, I know. It was more of an interactive movie according to some. But I think it has a really awesome story, so there. Sure, it doesn't always make the most sense. But I found it easy to overlook that because of the characters. Now, I've never played any of the other Final Fantasy games, so I can't compare, but even if I had, I don't think my opinion would change. All of the characters seemed real to me. Okay, not completely real (I look at you, Snow), but enough to make me care about them, and enough to make me feel a little bad for Hope at the end.

Oh, and Vanille's my favorite game character ever. Yes, I just said that.

Honorable mentions (but ones I don't feel like writing about right now): Knights of the Old Republic 1 and 2, Deus Ex, Alan Wake, and Max Payne 1 and 2.

The Witcher 2, FFS.

nuff said

Hmm... The Longest Journey and Dreamfall have one of the best stories ever told in video games history. I was touched, I almost cried at many moments...

Also, Syberia 1 and 2. Moving the imagination to the whole new level. Remember the ending of Syberia 1? I was crying like a baby.

I guess I'll be the 3197438176th person to mention Planescape. I really do love that game.

Sanitarium was decent, although gameplay-wise the second half was ass, which kind of ruined things. Also, the whole "save the children" thing was kind of stupid.

For one nobody's mentioned. Golden Sun (both GBA games). This is a strange one for me because normally I can't stand JRPGs, but the story on this one was very well done. Basically, the first game is pretty standard "kill the bad guys and save the world" fare, but the second game deviates quite strongly, both in terms of gameplay and story. Granted, the ending was kind of crappy but they always are.

Beyond Good and Evil... Eh, it was decent as games go, but it could've been so much better. The gameplay was far too action-based to go with the story and as soon as you joined the IRIS network, they pretty much told you exactly what was going to happen. Not to mention, it was way too short for a story-based game.

Knights of the Old Republic had a great story, but the rather incomplete nature of it ruined it. If it had been finished though, I daresay it would be a masterpiece.

Tex Murphy: The Pandora Directive.
I always keep banging on about this game.

-multiple and vastly divergent paths through the game
-6 different endings
-FMV done right
-multiple locations / items that aren't critical to the story
-one of the most engaging and interesting stories I've ever experienced in a game
-great dialogue system (a la "Mass Effect / AP" from what I read)
-occasionally hilariously funny
-interesting characters

Boys and girls, this game's got it all! In fact, may start playing it again tonight! Education be damned!

Not the best, but I'll throw Gemini Rue into the mix as well. Great little indie adventure.
I'll throw in another +1 for Cryostasis, because it does have a great story, but doesn't really get enough recognition.

Tex Murphy: Under A Killing Moon. This is just a fun story. Unique characters with fun personalities, with a fun story. A well told fun story.

Planescape: Torment. It has to be said. Everything that's great about this game has been discussed to death, but it's contractually obligated to be included in any discussion about great story in a game.

Batman: Arkham Asylum. The only game where you actually feel like Batman, like you're in a great comic story. It's told in a way that progresses into one hell of a long, trying night for the caped crusader, and you feel it yourself while playing it. The only downside are the bad boss battles. This game makes a great companion piece to The Dark Knight.

Uncharted 2. This is a great adventure story, with a pretty bad boss villain, but this game has a history of sucking with its end boss battles.

Yeah, i agree with this. The first part of the game is one of the darkest, creepiest things I've ever experienced (let say, to the "old house level") After that level I was thinking like I was playing totaly different game. It was silly, stupid and not entertaining. Like developers lost both their ideas and money and they made rest of the game from leftovers.

And the ending was just one of the silliest I've ever seen in any video games in my life.