Obviously, story/characters/dialogues is pretty much the most important aspect in adventure games. Puzzles are just a nice extra, though arguably still pretty valueable since they give you the impression you're an integral part of the story as it unfolds and not merely watching it(though Telltale's adventure games like Walking Dead have minimal gameplay, and are still a success).
Other than that, honestly I don't really care much about stories in games like shooters or RPGs. Maybe one reason is indeed that, as mentioned, most times the stories and dialogues just aren't worth it. When they're not purposefully "dumb", like in the recent Shadow Warrior remake(which I loved), they're just trying to pose as "serious", which makes them two times dumber. There are some exceptions, with Spec Ops: The Line being an obvious recent one, but at the end of the day I prefer gameplay over story in this kind of games. Supposedly Bioshock Infinite has a great story, but personally I still haven't finished it; after a few hours of pretty uninteresting shooting gameplay I decided I just didn't care. The game was basically divided into 2 parts, with the first being the cutscenes that progressed the story, in which you had almost no control and Elizabeth was an interesting character to watch, and the shooting sections which were merely adequate at best, and Elizabeth just functioned as a bot who occasionally provided you with ammo.
Making a good story with interesting characters that progresses naturally as you play the game and not getting in the way of the gameplay is hard; so as I said given the choice, I'll take good gameplay any day, even without any story at all. Honestly, I'm having more fun right now playing Doom2 modded with Brutal Doom than with any Bioshock title. It's not even "nostalgia", the game simply has more fun level design and shooting. If they had made the Bioshock games as first-person adventures like, say, Amnesia, then it would be another story entirely, but they made them first-person shooters, and when I spend 70% of the game shooting, I want it to be *good*, and it wasn't so much. Interesting story told through cutscenes just doesn't make it up for me in a shooter. Still much better of course than most "modern military shooters" single-player "campaigns" which have completely crappy stories *and* braindead gameplay, and basically no reason to exist at all, except maybe providing footage for promotion trailers. So I guess a good story, when it exists, makes me appreciate the game somewhat more even if the gameplay is mediocre, but most times I still won't consider it a *good* game.