I've also heard good reviews about Slackware as a server. It is supposed to be one of the more customizable distributions. I like Debian
myself. Debian 3.0 (Woody) is a seven-CD set, and Debian 3.1 (Sarge) is a 14-CD set. You only need one to install, because you can choose what packages you want or don't want. But Sarge should have just about everything you could possibly want for server software.
I can't speak for Ubuntu, because I haven't used it. But the more I hear about it, the more tempting it is for me to download and try it.