I liked the stealth elements in VTM: Bloodlines as it was a feasible option to most encounters and maps in the game. Similarly Fallout3/Oblivion have a reasonable system that does allow for player skill (and skills). The first couple of Splinter Cells were quite good too.
Hitman games have always had a cool stealth element too. Using disguises and hiding in cupboards, stashing bodies, being in places 47 isn't supposed to be in, and so on. But I think the Thief series have done it best. With cool AI, realistic consequences for Garret's actions and detail....what floor surface, how much light, how alert is the guard, calculating routes, using deception and cunning to sneak past and so on. A single wrong footstep can lead to failure. I found at times I was actually holding my own breath whilst a guard tried his damndest to find me.
Anyone who suggests Assassin's Creed as being a stealth game has not played an actual stealth game. The extent of stealth gameplay in it is avoiding easily dispatched guards.