As an avid fan of Thief, I would normally have said that Thief I and II are slightly better games. However, I'm currently replaying Deus Ex and it clearly provides more scope for different play styles than pure stealth. Thief is hardcore in that regard, Dark Project and Metal Age more so than Deadly Shadows. On the highest difficulty, no killing is allowed. In Thief, you can choose multiple ways of finishing a mission, but pretty much all rely on stealth. Deus Ex lets you play it as a standard FPS walking-tank if you want to (although you miss loads if you do). Thief has an awesome story-arc though, with some fantastic level design.
Thief requires a LOT of tender love and care to get working on modern hardware though. But it's worth it. If you want help setting it up, let me know, I have experience with helping others at TTLG with installing it :)
Some fun things for you all - you can do all of Deus Ex with no killing:
http://www.youtube.com/user/shido534#p/c/8B3C5852853469DF (although he seems happy to blow up robots). Also, here's Azal's guide to ceollecting silly things in Thief:
http://www.greywool.com/azal/
I'm not quite that patient - the average mission time is already about 1hr just to finish all the objectives.
Edit - Just to say, both Deus Ex and Thief I & II are top-100 PC games of all time, and can be obtained really cheaply - just get them :)