Not one month has passed since I was writing about the relationship between story and medium. Barely one week since Jay Barnson argued that in an RPG the dungeon itself has to tell a story. And here's an interview with Rhianna Pratchett reminding us yet again about the disconnected way in which AAA games get their stories. Namely as an afterthought, tacked on to generic levels and enemies.
I've heard people say that Planescape: Torment, a game much praised for its story, actually has a mediocre one that wouldn't pass muster in a novel. Perhaps. But what story it does have pervades every little corner of the game, to the point that dungeon fixtures and even an entire neighborhood of the city turn out to be self-aware NPCs with little stories of their own, in which you become enmeshed as opposed to merely hearing them out.
Take any game famous for its story (of which there aren't many at all) and you'll probably find that it shares this same trait: the story is integral and fundamental to its entire design. That, more than some vague notion of "quality", is what players notice and appreciate, even if they're not aware of it. That and agency: taking part in the story as opposed to being a spectator. Which doesn't fly even in "static" media; why do you think fan fiction is so popular?
The medium is the message, folks. Learn to see things as a whole.