Debian (use STABLE branch) is by far the best, most reliable, and most stable server distro. Expect to be a bit behind in software as things are very thoroughly tested before entering the stable branch. (You can always pull from testing, or even unstable, for one package if you need to.)
I love and use Gentoo, but... I would have to admit it's not the ideal server. I just know Gentoo so well that the added knowledge more than makes up for any shortcomings Gentoo may have. Gentoo doesn't backport patches to older OS releases, Debian does (Gentoo tells you to upgrade, which can potentially cause instability or incompatibility). Also, Gentoo doesn't have discrete releases like Debian... it's a rolling release. What you install on one day will most likely differ from the next day. Every time a new package hits, it's now part of the latest "version". I run full updates daily on Gentoo.
CentOS and Slackware are also stable server choices. CentOS requires more resources, Slackware is efficient. They both force you to use a more awkward packaging system (rpm for CentOS and nothing at all for Slack). On the upside, if software isn't in the repository (rare for Debian, Gentoo, Ubuntu, or other major distros), there's a better chance of it being available as an rpm than anything else since so many corps use Red Hat for the professional (paid) support. Debian is going to be more user friendly than the others. Ubuntu is very user friendly, but I prefer it as a desktop OS rather than a server OS, although they do have some options for configuring a PC more like a server.
BSD's also make great servers. OpenBSD for security, FreeBSD for larger community and ease of use. Nothing is more secure than OpenBSD.
That thing is stable as all heck without a gui.
QFT. With any Linux distro, running w/o a GUI gives you a dramatic increase in stability. It's probably a decent part of why Linux and BSD servers have uptimes that are orders of magnitude higher than Windows... you cannot get rid of the Windows GUI, and the GUI is what will cause the crashes in the vast majority of cases.