First, I'd recommend using a debian-based distro like Ubuntu. From my experience, it is much easier to use and configure, and the amount of tutorials, etc, available for it is overwhelming.
I just setup a vps with linode.com two days ago and chose ubuntu. It's been fairly trivial to administer remotely, without x. I haven't had to take on the role of an SA anytime recently, but it couldn't be much easier than to work with ubuntu so far.
I agree that it is easier to use and configure a debian-based distro, but I would add that if you really want to learn Linux intimately you should check out Gentoo. The Gentoo docs are really good and will take you through the setup step by step. By the end of it you will have configured and compiled your own kernel and have familiarity with a lot of the /etc config files. Of course things may not work out the first couple of times and you may just get so frustrated you want to give up.
The Gentoo documentation is absolutely astonishingly great. But it's the only aspect of the system that I consider good. Everything else is a mess.
Gentoo feels like someone sat down to a Debian or CentOS system, used it for a while, and said, "You know, I really like it when I have to compile stuff from scratch, and make all of my own decisions about options and stuff and what tools to use, even though I have no idea what the difference is between various init systems, FTP servers, versions of Apache, configuration tools, etc. I don't like how easy and quick installing software from apt-get or yum is, or how it all seems to Just Work when it's done. I know, I'll borrow some ideas from FreeBSD's far more complicated to use and error-prone package management tools, and make a whole new Linux distribution that requires significantly more time and effort to use! It'll be awesome!" And a billion and one nerds with too much time on their hands saw it, loved it, and climbed right on board.
I'm sure I'll be voted down for this, as Gentoo has rabid fans, but I'm always stunned by how effectively the community markets Gentoo to new Linux users, and what an astonishingly bad experience it provides to those new users. Encouraging learning is wonderful, but foisting a seriously challenging learning experience on to users while calling it an "easy to use" Linux distribution is doing them, and Linux in general, a grave disservice. Gentoo is not easy to use, and it is extremely easy to break.
I wouldn't recommend gentoo in a hosting environment until you're comfortable. I know a few people who completely hosed gentoo boxes during the learning phase.
Any popular distro with good package management and a long lifecycle is fine.
Of course, that narrows it down to Debian, Ubuntu, RHEL, and CentOS. But all of those are absolutely fantastic in current versions (though I generally like Debian better on servers than Ubuntu--I just don't think the changes they've made make it a better system).
Ubuntu server is cool (I use it on my machine). Also, the book Hardening Linux is good for the security side of things. I found online references to be best for setting up individual packages.