Well, I have P III 600 MHz, 128 RAM and 6 GB of space. It runs Ubuntu 5.04 currently and I tested SuSE 9.2 with KDE.
It's a little slower with full blown KDE and Gnome but it's still usable. I'd stick to minimalist GUI such as IceWM and stuff since they will take less resources.
If you want a little faster experience, stay away from KDE bloat since KDE will load a whole bunch of stuff at start up. If you don't mind waiting for a few minutes of system response time, then it's okay I guess.
It's still usable but just that it's a little sloowwwwww.