Here's what I like.
1. Fast pace. Spending 30 seconds in one position watching a guard walk by is not my idea of fun. It breaks some realism to allow the protagonist to run about full-speed without any noise penalty, but the amount of fun it can generate easily makes things better.
2. Binary determination. Are you VISIBLE or INVISIBLE? Are you meant to take out ALL enemies, or NONE of them? Will this attack WORK or NOT, and WHY? Many stealth games before Batman tended to have many "grey areas". The visibility meter, guards with different levels of awareness, different rules on who to take out (in some games, it's very unstealthy to take out every guard, but it's also impossible to accomplish the mission without some kills). Also, many games have your attacks on a guard either work perfectly or completely fail, entirely on the minor basis of whether they were facing a few degrees more to their left.
3. Information. If I have the extreme disadvantage of being alone, and forced to use silent attacks (usually even limited to close-range attacks), and I cannot be spotted when attacking someone, I kind of like having some perks on my end. Some easy way of knowing what's happening where, so I know how to respond and what traps to lay, makes the game much more fun. No one likes being snuck up on when they're supposed to be sneaking.
4. No pattern-recognition. This is meant to be something we learned in old arcade games; when someone can only beat a level by memorizing a series of button presses in the right timing, then it's no longer fun.
5. LOGICAL information for guards. If a guard heard a noise "over there"! Then he heard a noise RIGHT THERE. He should NOT home in on wherever the player currently is, at all. I'm reminded of a time in Splinter Cell I threw an object to the opposite side of a room to distract a guard. He stared at the point of impact...then walked straight towards me. Even if all guards have spotted the player and you're in combat, the game should not instantly decide that all guards should constantly be aware of your position. Splinter Cell Conviction got the right idea: Even in intense combat, it is commonly possible to disappear from your last known position.
6. If darkness is a big part of the game, keep your promises about destroying light sources.
AvP, 2 minutes in: Destroy light sources to make areas dark.
AvP, 2 hours in: The bad guys have invested in BULLETPROOF LIGHTS!!! And lots of them!!
Splinter Cell Conviction, 2 minutes in: Turn off or destroy lights to make areas dark.
Splinter Cell Conviction, 2 hours in: Destroy all 17 of these lights in this tiny office area to make half the room dark, whereas the 87 lights in the main hallway will still spill in. Then mercenaries will detect you in the dark anyway.