I think good choices could be RedHat or Suse, but I'd recommend Mandrake 8.0

• The installation is one of the simplest I've ever seen.
• As it's RedHat based, you can use rpm if you want to
• 2.4 kernel
• Perl with some useful modules...
• Pre-made setup (Server, Workstation) AND custopm setup
• A lot of useful SysadminTools (sometimes lacking in other distrib) available (Tcpdump, nmap)
• Active distro, excellent Website : with frequent updates/patches, mailing-list...

What I really like is that a lot of things are automatically installed with the pre-made setup (ssh,Apache with PHP/Mod_perl,MySql...)
It's also its main default : you'll need a big disk beccause A LOT of tools are installed
(Or you'll have to spend time to carefully choose which one you want in the expert setup...)

The other drawback is that Mandrake use by default a non standard kernel
(more accuratly a kernel modified for security) which requires special patches (or requires you to install a standard Kernel))

Now if you're not sticked to Linux, you should give a try to OpenBSD 2.9
The install is the simplest and the fastest I've ever seen
(far beyond Windoze, or linux distros...)
5 min is all you need (!) to have a SECURE server
(ie: ready to go online and stand all the script-kiddies' attacks...)

"Only Bad Coders Code Badly In Perl" (OBC2BIP)