I'm pretty excited about Bioware's new RPG Mass Effect. I've only played it a bit so far but I'm already knee-deep in the story. The action combat gameplay is meh, but the storytelling is fantastic.
What makes the game work is the interactive dialog engine. Meeting a new character is more than just waiting for a cutscene to offer up some crucial clue; instead you enter into a little narrative puzzle trying to figure out what to say to get the character to do what you want them to. It's very simple technology, mostly a branching path of dialog nodes, but that interactivity makes all the difference. And as icing on the cake, the moral choices you make in the dialog influences your character's development.
I don't understand why more games don't tell stories this way. Bioware, Black Isle, and now Obisidian have been doing it for years. And what a string of hits: Fallout, Baldur's Gate, Planescape: Torment, Knights of the Old Republic, Jade Empire. All much loved story RPGs and all using the same dialog structure. Why don't other game developers do this? The only non-Bioware affiliated example I can think of is Deus Ex 2.
It's a simple storytelling technology, but that constraint seems to liberate the writers. It's a bit like Infocom's Z-machine where the story engine is simplified enough that it gets out of the way. Of course games still require great art, backstory, and writing. But the little dialog engine is key.
See also Eric Tilton's comments