People who have lost any time reading my reviews will have noticed that I'm a bit of a story snob. I love games with good stories and will overlook a lot of faults if a game can give me a few endearing characters or a satisfying ending. The other side of that ever-spinning coin is that I'll savage a game if the characters are repugnant, the story is full of holes, the premise is ludicrous, or the ending fails to tie things up. This is true even if the gameplay is good.
I'm not saying all games need to be packed with characters and plot like The Longest Journey in order to have a "good story". In fact, sometimes less is more. To illustrate my point I want to use one of the very best cinematics from the last few years, the intro to Left 4 Dead. This four and a half minute clip shows a skillful and extremely economic approach to conveying information to the viewer while delivering solid movie thrills. You can deconstruct the thing shot-by-shot, line-by-line, and see that every moment fulfills a purpose and adds to the whole. Everything that is said or shown is there to introduce the world, set the mood, establish the personalities of the characters, or teach vital gameplay mechanics. Often it accomplishes several of these at once.
It is because of this efficiency that the final product is so entertaining. The writers didn't just design a big fight scene and then try to shoehorn in some stiff dialog about how the zombies behave. Unlike a lot of videogames (and some movies) they don't use action as a sugar to cover up the bitter medicine of plot exposition. The two work in harmony, and each makes the other more enjoyable.
The other noteworthy thing about the story in Left 4 Dead is that there isn't much of it. There is exactly as much as we need for the game to work, and no more. Once the particulars are set up, the story doesn't keep shoving itself to the forefront and getting in the way just for the sake of trying to be like a movie. The designers didn't put in an ongoing plot where you chase around some mustache-twirling idiot of an antagonist who engineered the entire zombie plague and now wants to kill the survivors to complete all the items on his "clueless villain" checklist. They didn't put in some "obvious traitor" side plot. No global conspiracy. No author-insertion mystery oracle to deliver exposition. No awkward love story. Nothing about saving your parents / children / significant other from the threat. The story is small, lightweight, and packs enough punch to set the mood and tone for dozens or even hundreds of hours of multiplayer zombie-smashing.
Often I take a popular game and deconstruct the plot, talking about the character inconsistencies, plot holes, bad pacing, forced exposition, hanging plot threads, and just plain old cheesy dialog. The response from die-hard fans will invariably be to point out that "games are about gameplay". Which I guess means you can't ever criticize a story ever, no matter how lame or insulting it is?