There's always Hitman, those games have their highs and lows. Unusually enough, Hitman 3 is actually better than the previous two games. Go figure.
I'll vouch for Thief a dozen times over.
I had a lot of trouble playing the scarier missions in 1 especially the cathedral, the horrible horrible cathedral.
Thief 2 is a more living, killable, ordinary people based. Which I suppose makes it a bit duller in a lot of respects, but I liked spending less time cowering in fear in a dark corner while I wait for the evil things to go away, and more time lurking in a dark corner, waiting for the guards to turn their backs. Plus it had a whole bunch of gadgets, and such.
Thief 3 I quite liked, I don't think it was really that much easier than the previous games. Walking around the streets, picking pockets was pretty fun. Although it got irritating when they got filled with evil bad guys constantly trying to kill you (you then of course, have to make your way through those streets as usual, only now people are being killed left and right, and yet they try to act like everything is normal). I wouldn't have minded if they just kept stepping up street guard patrols, but that wasn't to be.
In any case, they levels were quite fun (if a little boring at times, and yes, they could have done with ramping up the difficulty more). The engine flowed very smoothly. Mostly I'm talking about snuffing out candles, which was fun, and the backstabbing, which was infinitely better and more satisfying than the awkward "hit them with a sword and hope it kills them correctly" system... Although of course, the pros always use the blackjack. Or they snipe them out with arrows.
The one thing I'd hold against Thief 3 is the lack of rope arrows, they were so much fun! They've got climbing gloves instead, which are a dumb metroidvanian mechanic.
... oh, and the cradle the horrible horrible cradle.