Like others said, different games do different things so we can't give them a single formula to stick to.
One thing I hate though, is when I say I like a game's story getting responses like: "if you like stories then read a book or watch a movie, this is game!". Of course, that's nonsense, and it's not unreasonable to expect that a game that bothers having a story also has a good one.
That being said, if a game has a good story it wouldn't be the same thing if it was a book or movie, if it was we'd have seen better adaptations by now. Games are a media inbetween books and movies: it has the advantage of the image like a movie, we can see that building, or that look or smile a character gives another that in a book it would take so many words and still might not convey it properly. But, like a book, we dictate our own rhythm; a movie keeps moving forward despite of you, but in a book you can savor every word and sentence for as long as you want, reread them, explore the writing in a way; games do that as well but in a more physical manner, even such a linear game like Bioshock Infinite gives you the option to stand still instead of moving forward, take a breath, walk into a sideroom and see or hear something interesting. So a story being made into a game, instead of something else, does have its advantages and I try to take them as they are.
On a side note about the other topics being discussed here: I very much liked Dishonored and, despite some lackluster voiceacting, I did enjoy the story and how a lot of it you experience naturally during play. I didn't enjoy Skyrim in that regard, it is fun thinking about all the crazy things that happen with you, like: "I was collecting butterflies on the forest when a dog came up to me and started talking!", but they feel more like shallow anecdotes than proper stories.
I do not mind a strong protagonist in the lead, in fact a game that I very much love, Red Dead Redemption, has one and I liked him so much that I made a point of never commiting a crime during my entire playthrough because I wanted to honor his desire to leave his criminal life behind. It was probably one of the few times where I actually role played in a game.
Finally, I hate it when a game gives you a cutscene when whatever it's showing could have been done in-game instead, part of why I seem to enjoy radio conversations in games.