BillBrown hit it on the head. It's really all about preference. I started out working with RedHat servers, and then experimented with every different distribution I could get my hands on until I discovered the beauty and elegance that I like to call "apt" (the package manager used by Debian (and debian-based distros)).
I use Debian for all my server applications, and xUbuntu for my desktops. BUT it's all about preference.
In my personal experience, Debian makes a reliable, easy to manage (if you're comfortable at the command line) server. There are also graphical configuration tools, but I'm not that familiar with them, so I don't know how a new user would find them.
If you're not that familiar with Linux yet, and want a shiny web-based interface to help you get things set up, the "SME Server" distribution is really nice (or it was the last time I used it, at a previous job). Especially if you're running it in mixed (Windows and Linux) environment.
RedHat/CentOS based distributions are also very stable, but their package repositories are not nearly as complete as Debian's, and trying to resolve rpm (the redhat package manager) dependencies manually can be a nightmare. But they do provide some nice graphical configuration utilities if you are planning to run a graphical desktop on your server.
Fedora can also be used as a server, but it's the "bleeding edge" RedHat distribution, and in my experience is not stable enough for a production server.
Installing Gentoo will teach you everything you (n)ever wanted to know about Linux. Being source-based, it can be as light and efficient as you care to make it, but it hasn't made the easiest to manage server in the environments where I've had to use it.
I won't speak on SuSE... I know people who have used it with great success in server environments, but the way SuSE is configured is just not intuitive to me...
Slackware is always an excellent choice. It's "pure" Linux. It's reliable and stable, but notoriously difficult to manage.
I have the same issue with Mandriva (Mandrake) as I do with SuSE... I have a friend who swears by it though!
I think that covers all the major ones... Forgive me if this post was too long

I like to see folks trying Linux, so I like to help them pick the distro that works best for them. Picking one that's not easy to work with, or doesn't fit your style, can make it a frustrating experience for the fresh Windows convert. These are all my personal opinions, so anyone is free to dispute them, but I try to be as unbiased as possible
I hope this helps!
-G