I'm an avid FreeBSD fan, I've installed FreeBSD setups similar to what you're looking for on a variety of machines ranging from 486 DX4/100 to an AMD XP1700.
The FreeBSD docs are great and the best part about the install is you only have to download 2 floppies to get started. Then, after setting up your NIC the installer itself only downloads exactly what you need based on your choices.
Personally, I've find the FreeBSD package system easier to work with (especially when upgrading months later) than the Redhat RPM system. Also, the FreeBSD ports collection is extremely helpful if you want any easy way to optimize and compile apps specifiacally for your system. In general, I've found it very easy to tailor FreeBSD for low-end computers.
If you go that route, I'd recommend FreeBSD 4.8 (the 5.0 branch is brand new and lacks some compatibility still with older hardware).
WARNING: The State of California has found the above statements to cause cancer and OS flamewars in labratory mice.
FYI, everything described above can prolly be done with any 'NIX distro given sufficient knowledge and time. I've simply attempted to briefly describe my preferences based primarily on anecdotal evidence and personal experience.