Having already given my two cents on non-linear storytelling models, (that until most game studios change their opinion about the importance of storytelling in a game, trying to expand the paradigm will be largely wasted) that begs the question of what makes a good story. That's a huge question, and I'm not gonna try to tackle it, but the least I can do is talk about my preference.
I've always been partial towards character work. Interesting twists of fate and a good world to immerse yourself in have never been as engaging to me as a good character arc, plotted out with careful attention to the character's past, conscious objectives, unconscious objectives, and culminating in a profound, satisfying change. “Satisfying” in this case doesn't need to mean a change for the better, merely that the denouement scratches the itch that the writer has coaxed out of the gamer ever since the direction of the character arc becomes clear (this begs the question of non-linearity again, but we'll save that one).
Talking about creating a dramatic situation that demands satisfaction in the gamer is very much screenwriting language. The classic thought on the matter (though by no means the only one) is that you have to give the audience (interchangeable with “gamer” in my mind) what they want, but never in the way they expect. In “Die Hard”, if John McClane was never helpless at the hands of Hans Gruber, you'd feel cheated out of a good time. In Portal, at the end of the final test chamber, if you exited the facility with nothing more at stake, you'd feel cheated. And yet, if you were able to predict that (ZOMG SPOILERS) the main character of KotoR is Darth Revan, you felt a little disappointed when they revealed it to you. Likewise, you know that Bruce Willis has to beat Alan Rickman's character somehow, but if you guessed that he had a gun attached to his back with Christmas stamps, you'd be disappointed when the camera panned over to reveal it.
To reiterate, you need to give the gamer what they expect, but not the way they expect it. This requires a careful eye towards what you are coaxing the gamer to expect, which is the best argument I've ever heard for some kind of a narrative mastermind involved in a game. In an expertly directed game, everything should coax the player into anticipating the climax. A simple example: In a throne room, everything should direct the eye towards the person in the throne; the music should indicate a presentment; etc. etc. Though the player may not know exactly what position the throne bearer occupies, the general feel should be clear before anyone opens their mouths.
A more complicated example: In Final Fantasy VII, a lot of people were put off by the sudden introduction of Cloud's severe ontological crisis. It more or less came out of nowhere. There were some vague issues of Cloud not remembering some events, but it didn't seem to bother him, and weren't played as bearing any real importance. Suddenly, when his emo streak becomes crystallized in the form of “I am my own monster!”, people were left scratching their heads.
Final Fantasy VI, while prey to the cliché of “main character who can't remember her past”, let you know from the very beginning that Terra is going to have to resolve the question of who she is before she can meaningfully interact with the world around her. She resolves the issue of her physical heritage, but it's not until the orphanage in Mobliz that she is brought face to face with the issue of who she decides to be. The struggle in Mobliz is her realizing that her power, even her power to destroy, can be used for good. Again, an aware gamer will see this coming. The entire game hangs on the edge of whether mankind can be trusted with the power of magic safely, and Terra has her own issues to resolve, from her period as a victim of the slave crown. I'd love to launch into a discussion of Fei's issues with exercise of power in Xenogears, but that deserves its own essay. Suffice it to say that in Xenogears, while all these crazy outside events are going on, much of the game is designed to continually force Fei into reconsidering his position on the exercise of power. While you watch events unfold, everything tells you subconsciously that Fei is going to have to deal with this issue once and for all.
That, my friends, is my favorite kind of story. I've already stated that I'm partial to engaging character arcs, but what really seals the deal for me is a fascinating envelope that helps the character arc along. For all the epic science fiction in Dune, it's about Paul embracing the mantle of a messiah. For all the bizarre comments on human nature, Kino's Journey is about a girl who ran away from her conception of adulthood. For all the acrobatics, the newest Prince of Persia series is about the Prince realizing what it takes to become a man. For all the apocalyptic events, Xenogears is about Fei resolving his issues with his mother enough to embrace Elly as an equal, as opposed to a surrogate mother.
This is not meant to downplay the intricacies of the external plot developments. Portal is not known for the complex character arcs, Gordon Freeman is a relatively implacable character, and any MMORPG features completely inaccessible PCs, but that doesn't mean World of Warcraft doesn't feature an incredibly engaging world. I'm merely stating where my preference lies. Next up, magical realism, and the best kind of character development.