What do you look for in a Stealth game?
Self-explanatory.
Consistency is the biggest thing for me, and this applies to nearly everything. If I throw a bottle behind an enemy, that enemy should always investigate the exact same way, provided I've thrown it in the exact same spot each time. If I restart a checkpoint, even if I restart it ninety times in a row, all enemy placements, patrol patterns and timings should also be consistent, lest I feel cheated out of my fair mastery. Consistency also means, if I can throw a bottle at a wall, but I can also shoot suppressed shots at a wall, or throw knives at a wall, ALL of those things should cause some manner of investigation of that wall, with a fair degree of consistency.
AI Manipulation comes next, and honestly this should be at the top of the list, because it's what separates a Stealth game from a game which pretends to be a Stealth game. AI Manipulation is essentially, the ability to play with the AI in ways that are beneficial to you, that do not involve removing them as a threat but manipulating them to act in certain ways, allowing you to make your way around them. Distractions are the one everyone's familiar with, and these can be done in all manner of ways. From throwing stuff around, to having them investigate bodies and corpses, to having them catch a glimpse of you and want to come check it out.
Non-Lethal Gameplay is third. It's not always necessary, but a Stealth game which facilitates Non-Lethal play is, in 99% of cases, simply a better-designed Stealth game, period. Whether this means not having to touch anyone, or being provided with the tools to make sure that, when you do touch them, that touch is not deadly, if a Stealth game is designed to have wiggle room for Non-Lethal playstyles, that is also hugely attractive to me.
Bring forth thine opinions! Would love to hear from you all.
If I restart a checkpoint, even if I restart it ninety times in a row, all enemy placements, patrol patterns and timings should also be consistent, lest I feel cheated out of my fair mastery.
Disagree. And not just my usual devil's advocate disagree for the sake of discussion. 
That. would. be. boring. Just play Super Mario Brothers if you want the enemies in the same spot every time. (Or revelations where you could eagle sense the patrol routes).
I would rather have super well-defined AI actions and super well-defined ways to manipulate those AI actions.
In STORY missions, it is acceptable to have the KEY enemies in the same spawn points. However, even in real life, if you stake out a place there's no guarantee that the patrol will behave identically every night. Maybe a guard is sick and walks slower. Maybe he had one too many monster energy drinks and his more keen to sounds so responds quicker. Maybe it's a new guy that's super keen to do things right but doesn't execute and cover escape routes well. Just as examples of how people are not machines.
As long as there are fully realized and well defined ways to manipulate the NPCs, I don't care where they spawn. It makes it more interesting in later plays. (I know, speedrunners and the like would hate the randomness involved).
Full disclosure: I'm not saying that enemies shouldn't be consistent in spawn points and actions. I'm not going to that extreme and saying full random is preferred. What I'm saying is that it's not at the top of my list.
Well defined ways to use the environment and your tools to manipulate the enemies in predictable ways is tops on my list. I'm not saying that you need to master the exact distance behind a guard to throw a bottle to elicit defined reactions. I'm saying that, in a first playthrough, I should be able to predict what will happen based on my knowledge of the real world. I know that if I throw a bottle, someone will notice it directionally. I should know this from my real world experience, not because a game pop-up tutorial told me so.
Predictable, consistent, well-defined AI actions and reactions to player influence and it doesn't matter where the enemy spawns or which way he is walking - you can change those variables with the right tools.
“Force has no place where there is need of skill." Herodotus