Punitive : I expect from a stealth game to be really punitive, and make the player understand that he has no chance if he goes the “hard-way”. And if he do, then he have no chance of survival.
Fair : If the player is spotted, it must be his own fault, there is nothing more frustrating than an unfair game. For exemple, AI spotting you because you hid behind a box which apparently cover your whole body, but the collision box does not concur, so it’s like the AI can see through the box. Or when an AI hear you because you made some noise 2 floor below (it happened to me in Deus Ex)
Make you awesome : The game have to give you chance to be an awesome and daring stealth ninja of the death. The level design has to propose you some path which may be difficult but really cool to take. Path which make you say : “There is three guards, it’s nearly impossible, but I can do it”… Ok, I don’t have any exemple right now and It is maybe not very clear. But if I had to say an exemple it would involve : diversion, throwing shuriken, wall runing, and maybe some unicorns.
And I think this is a good start (maybe)