Not sure what you are doing but I have clients that are running webservers on 486's with 64 megs of ram and the speed is just fine. One problem I have noticed over the years that may also apply to you, is the video card.
Some cards will make Linux run very slow if you are using Xwindows. Try replacing the video card with one of those cheap 32 meg pci cards. You can always return the card if it doesn't work.
Also for you MIS people out there you might want to look into Linux/VMware. Using this combo you can install most OS's on a Linux server base, including server OS's, and use them remotely from a cheap desktop or the internet(vncserver+fairly good connection)
The other upside to this is that if an OS fails, if you are doing the proper linux file backups, it can be reinstalled and up and running in 30 minutes or less.
I do not need a heavy weight desktop all I do is write code compile/test and run a few servers (apache/jboss/tomcat/mysql/etc) but I do want X-Windows to be available. I also want a nice interface to admin function like network configuration etc.
Not sure I am making sense here, but I think it is the heavy weight desktop that is slow not the OS. Now graphic card could be an issue. W2K does not like my grapic card either. LOL.