My favorite games tend to be action, adventure or RPGs.
My preferences really depend on the sort of game I'm playing.
For action games I like quick movement with simple controls rather than complicated combo systems. That way the complexity of gameplay comes from clever level design instead of deciding whether to press X-Y-X or X-Y-Y to produce the exact movement you need for a particular enemy time.
Also I like a pulled back camera way more than first person perspective, because constantly worrying about getting killed from an enemy you can't see behind you is a huge annoyance.
For story I like the 'Less is more' style of storytelling. If you've ever heard the expression 'Don't tell me, show me' applied to movies, I feel the same way about games. I like games that show you the story through the world design and a minimal amount of dialog rather than through long indulgent cutscenes. For example, I like Shin Megami Tensei: Nocturne's approach to story more than Final Fantasy XIII's. And I love it in games like Super Metroid and Zelda: LTTP how they express the story elegantly by the visual design of the areas.
For RPG combat, I don't care if it's turn based or action oriented, but what I can't stand is not being in control of your full party. It's one thing if it's a game like Tales or Star Ocean where you have such good control over your control character that you can pretty much handle the battle yourself + healing support. But if it's a game like Xenoblade where you don't have much physical control over your character and you also have zero control over your allies, that's just ridiculous. Any strategic options you have in battle, the player should have full control over their behavior.
Also, hidden items. Hiding things in cool places that can be logically figured out, like the SNES DKC games, good. Hiding things in random places you could only ever find by checking every little random corner in the level and forcing you to get 100% of them to get to the hardest levels, like the newer Mario games, very, very bad.
Difficulty, hard enough to force you to be skilled at the game in order to win, but not so hard that it's cheap and can only be beaten through grinding, brute force repetition and/or save states.
Handholding is right out and can ruin a game for me completely. Teach me new aspects of the game by presenting them in a context where I'm forced to use them naturally, don't set me aside in a 45 minute segment and give me hints for how to do things I should have to figure out myself.
And I love block puzzles and switch puzzles. Lufia 2 is one of my favorite games.