I think when it comes to stories, most video games suck. The actual storyline is usually unoriginal or cliched and predominantly stick to sterotypical tropes associated with that particular genre of fiction. Even JRPGs suffer to some extent becuase they apply a lot of sterotypes from anime. The only game I can think of with a truly original and thought-provoking story is Planescape Torment (although I've yet to finish The Longest Journey so I can't comment on that).
The more interesting aspect of video games as a storytelling medium is the interactive nature and trying to tell the story through the world and gameplay. This aspect is completely unique to video games and should really be utilised more frequently.
Half-Life 2 (and a lot of Valve games like Portal) are very good at this. As you explore the world tit-bits of info are given to you and it retains the first-person perspective throughout so you're never taken out of the world. Character speak directly to you and never in a passive, out of control cut-scene. When you do lose control it's because your character has lost control and the feeling of helplessness is portrayed quite effectively to the user. ICO and Shadow of the Colossus are other great examples of games that tell the story through the gameplay. They have some cut-scenes but the emotion is purely delivered through gameplay.
I think the world most games create is also more important than pure story as it immerses the player more than just story and chracterisation. Deus Ex is a good example of having a deep, interactive and involving world; whilst it has a great and twisting story, the world is what makes it so immersive.
