[JackVanian]

To me the Gabriel Knight games are the perfect example of what interactive storytelling can achieve in theory. I still remember when I played Sins of the Fathers for the first time. My whole world was turned upside down, because for the very first time I realized how much potential this medium has as a mature platform for "real" storytelling. Unfortunately there are nearly no adventure game developers out there that make any use of this potential which is quite a shame, 18 years after the release of the milestone that Sins of the Fathers was.

Other games that impressed me from a storytelling perspective:
Heavy Rain. One of the most immersive things I've ever experienced. A great demonstration of how you can provoce complex emotions in a game.

Then there is the Last Express which has already been mentioned on here. Nothing more to add, truly a brilliant piece of art.

Then I'd also like to mention The Pandora Directive. At the first look, the story is totally trivial (Aliens, Roswell, conspiracy), but when you have a closer look at the script itself it is quite impressive to see how much depth the story actually has - at least for a computer game.