Hmm. I play different games for different reasons, but I definitely appreciate good stories more and more. I suppose that might be because I grew up playing games like Rock N Roll Racing, Mario (duh), Mario Kart, TMNT, Robocop, etc. Then on N64 I started playing slightly "deeper" games are realized how much more interesting a game is when you're really into the story too.
Gameplay is still crucial, but I can barely play mindless games any more, except the occasional racing game or a bit of online FPS - both of which I get bored of fairly quickly.
I still love FPS games, which is probably why Skyrim and Fallout 3/NV are among my favorites. Great gameplay, great stories, and it's all in first person

I also really loved Metro 2033, and a little less so but still really really enjoyed STALKER: Call of Pripyat. Bioshock 1 and 2 were of course excellent. Listened to every single audio tape I could find. I even quite liked Deadspace, and learning the fate of the Ishimura as I progressed. Deadspace 2 wasn't near as good in story, but still fun at least.
Also, just throwing this out there - anybody else wish there could be a new Myth? That was by far one of the best and most challenging RTS games I've ever played, and it even had a tangible story. Starcraft would be runner up for me, loved the original... not so much SC2.