I think games work best when they focus less on an overarching story (as a movie or book would) and more on a world to immerse a player in. i.e., I think that the story and lore of the game's SETTING is more important than a narrative plot. This plays on the strength of the video game, which is exploration and discovery.

Coincidentally most of my favorite game series (like The Elder Scrolls, Warcraft, various strategy games and so forth) are ones that just sort of dump you in the world and let you traverse it and explore it on your own, making up your own story, character, and motivations as you go. When it comes to that type of storytelling, I would say that my personal experiences playing games are more profound than the majority of my experiences with other media.

But as far as a linear story goes, I don't know if I've quite found one yet that really comes close to really-good-book territory. Deus Ex probably comes really close.

But yeah, for me at least, I think video game stories work best when they are made up by the player.