Considering the games you've listed there's a good chance you've played at least some of these (and I've left out some that I'm pretty sure you've already mentioned playing), but anyway...
On the RPG front:
Vampire Masquerade: Redemption (with fan patches/mods... the original even patched is still a horribly buggy mess).
Pretty much any game by Spiderweb Software/Jeff Vogel
Betrayal at Krondor (brilliant game but showing its age)
showing its age)
Deus Ex (Primarily 1 but 2 and HR have some interesting ideas/concepts)
Dark Messiah of Might and Magic (a really good hack/slash RPG)
Anachronox (criminally underrated RPG)
In other genres, Sins of a Solar Empire (a sort of 4X/RTS hybrid) has no "story mode" or the like but a vast amount of pretty well written lore. Thief 1 + 2 are both great and Psychonauts (a brilliant platformer) has an excellent setting and atmosphere.
Edit: Should chuck in System Shock 1 + 2 as well... truly brilliant atmosphere in both games.