Jinxtah: I did try Dishonored, and I really didn't like it. Oh sure it starts off strong, but before long you're so infused with powers that you blink across maps and nothing poses a challenge anymore. It goes from being a stealth game to being a ... I'm not sure how to describe it, but they went too far with the powers I felt like. Enemies spot you? Np, juts blink away a couple of times within the span of a second and you're safe. Then come back and activate your insane powers and everyone is dead without you having to engage your brain. I think it would definitely be a great game if it wasn't for those overpowered skills though. I did get quite far into it, before I just couldn't take it anymore.
About Dishonored - if you didn't want superpowers (like Blink), why did you take them when the Outsider offers you the chance to either take them or don't take them at the start of the game?
To get the purest stealth walk-through, you'd probably have to go "no powers."
GreasyDogMeat: The same devs of Arx Fatalis also created the new Prey game. Has absolutely nothing to do with the original unfortunately, but it is a great modern version of System Shock 2 which others have pointed out is basically a sci-fi Ultima Underworld. Arx Fatalis was originally created to actually BE Ultima Underworld 3 but it didn't work out. The king in Arx Fatalis should seem very familiar to anyone who has played the Ultima series.
I'd basically recommend anything that falls under the genre of 'immersive sim'. Unfortunately there are very few games that fall under that category, but the games that do fit are often considered "good" to "one of the best games ever!".
-System Shock I & II.
-Prey.
-Deus Ex series.
-Thief series.
-Ultima Underworld I & II.
-Vampire the Masquerade: Bloodlines.
-Strife (old Doom engine RPG/FPS hybrid. Might scratch both itches)
-Alpha Protocol. (the main character kinda sucks but highly reactive to player choice)
-Dark Souls series. (Highly inspired by old school dungeon crawlers like Ultima)
Fantastic list right there, if you ask me.