This is an old thread, but I figured I'd throw in my two cents since this is something I've thought about a fair bit.
I think that the main thing to consider about games as a medium is that they're interactive. This has been touched on by others in this thread, but my point is: how can you leverage that interactivity as part of your storytelling? We've started experimenting with that already; any game with multiple endings or a morality system can attest to that (even if both those mechanics are currently severely limited in the best cases). In those cases, you've affected the ending by your own play.
But we can go a little farther than that, I think. Take OFF, a French RPG where you control this guy called the Batter. The game makes the distinction very clear: It's not that you are the Batter, you control him. It's a quirk of the game's fourth-wall-less storytelling (which, at the risk of introducing spoilers, becomes more important to the story at the end of the game).
Now, I have some things I could say about OFF and the way it handles its own gameplay in service of the story. :U But if you can get past the first boss (sigh), the story really does leave you with a lot to think about regarding your agency in the game, and I think that angle is one that we could explore a lot more in game stories.
...
Aside from all that, one of the things that's been brought up (and which I REALLY enjoy) is when the game has a story that it leaves you to discover on your own. That's really just interactivity leveraged in another way: rather than feeding you the story all at once in a particular order, you can find it out on your own, at any pace you like. In some cases, you can even ignore the story to complete all the challenges, if that's your style. You're just put into this world and can enjoy it at your own pace. And that's what I, at least, really love about games: the potential for exploration, the ability to just take in a setting and infer from it what you will. Is that a lot of work, as Salmoneous said? Yes, but creating something that's good and worthwhile is nearly always a lot of work.