I second Fable and Bloodstalker for Planescape Torment.
As for Deus Ex, quite funnily, I disagree with DesR85. I did not consider it more RPG than FPS. The feeling is the feeling of a FPS, the way your character moves, the way you kill people, etc., but the big difference between Deus Ex and most FPS is that in Deus Ex, you
do not have to kill everybody. In fact, in Deux Ex, you don't gain any experience for killing ennemies, so you can concentrate on the story and kill only those you absolutely need to kill. There is a good story (and I mean good, not very good, not average), almost no character creation/advancement, not much choices to make. The way I describe it, it may not sound very fun, but it was. I don't enjoy FPS very much (I found Half Life
extremely boring), but I enjoyed Deus Ex. I hated it in the beginning, because I thought I had to kill everyone, but while advancing and realizing I could just move and get into the story, I enjoyed it better. Anyway, you can get it on ebay for 5 $, so you don't have much to loose.
Have you played the Fallout series? If not, you should consider it seriously.