I like Gnome purely because I can't live without Nautilus (with scripts) and Gedit. For my server/workstation I installed base Debian and then installed just the minimum to run a desktop with my required apps. I like that approach because I end up thinking about what I really need and then have to learn those apps in order to maximise my experience.
I have described what I did at
http://www.kmeckstein.com - the article name is
A server with X Appeal - Please bear in in mind that I don't profess to be an expert but I am happy to share what has worked for me (after all, it took me some time to find out to find out how to make it work - if I can save other people that time, why not?)
Getting back to my server/workstation - It runs very well on a 1.4GHz pentium with 512MB of RAM (although I run it on another machine, faster, machine at the moment) - in fact, under those specs, for day to day purposes it runs faster (from a user perspective) than my main machine (a new AMD something or other with 3GB of RAM) with a standard Debian Lenny install!
If you can handle the interface (it takes some getting used to), and are prepared to move away from REAL Debian, why not try Crunchbang - on the same 1.4 GHz pentium (that I mentioned earlier), that really flew!
All the best
Keith
P.S. Your comment ...
"The preinstalled Windows XP just wasn't working...." - hate to tell you this but... XP is made that way!

P.P.S I became a Debian/Ubuntu convert after buying a new PC (I live in France and can't get to grips with an operating system in French), and immediately wiping the pre-installed XP and installing Ubuntu 6.10 - it's difficult to quantify but I felt that the machine became 3 times faster, as a result. Never looked back! Debian or die!