I'd choose two different game stories for two different reasons. Ace Combat 4 had a great little story. It was simple, which is good in a game story. It also chose just the right perspective for the events of a game - a child from an occupied territory. The narrative only deals with your accomplishments as they relate to the war as a whole, and the occupying pilots stationed near the narrator's home. Those pilots are expressed as humans - good people - that just happen to be on the other side of the war. They're pretty cool people, and I found myself regretting they were on the other side of the conflict.
The Longest Journey also had a fantastic story. This, more than any other game, feels like a folktale come to life in game form. It's fantastic, funny, and sad. It's important, because it doesn't feel like a book, or a play, or a movie. It feels like a game, through and through, but like a game that finally has found a way to express a really good story in its own unique way. The characters are also fantastic, and April Ryan is perhaps the best heroine (or hero) I've ever encountered. A lot of this is because she seems so... normal - or natural, which would be a better word.
Complex game stories (like in MGS) seem to deliberately gloss over (or leave out) information for the sake of setting you up for some arbitrary plot twist. I can't stand these. It's like they assume I'm an idiot who will mistake a gazillion plot twists for a "good" story. I don't buy it. You should be able to tell your story better than that, and plot twists should not be absurd - they should be meaningful and, ideally, obvious in retrospect. Plot twists aren't good when you can't possibly see them coming, they're good when you *don't* see them coming - there's a difference. In the latter, it's something you missed, and you consider the clues in retrospect - like Bruce Willis in The Sixth Sense. You could have seen that, but you don't - it just seems so obvious in retrospect. That said, I wouldn't qualify one game story as the "worst" of the lot. There are enough crummy little games out there, where the developers put no thought into quality narrative, that deserve the title - I try not the play them.