Hi emaderam, first of all Welcome to WebmasterWorld!

The choice of a Linux distribution depends heavily on the type of usage you are planning. Fedora is the fastest in adding and updating drivers for new hardware and features and is therefore the best if you want to have the support for the newest gadgets. But the drawback is that with every update new bugs may enter your system. The second drawback is that the Fedora support window for a given OS release is often shorter than the planned usage time of a rented dedicated (VPS) server. As hardware support is not an issue on dedicated servers, I would therefore not recommend Fedora.

Ubuntu is the most user friendly and is a good choice for a desktop oriented system. Community support is good, but it suffers the same problem as Fedora. The support window for a given OS release is often shorter than the usage time of a server and critical updates may not be available after a few years. The good thing is that some of the releases are LTS versions (Long Time Support) which are supported longer than the other versions. If you plan to use Ubunto on your server, be sure to install an LTS version.

CentOS is a repackaged and community supported distribution of Red Hat Enterprise Linux (RHEL). RHEL is a commercially supported distribution mainly used on servers and many server manufacturers have driver packages for their specific hardware (disk controllers, network cards etc). As these RHEL packages are binary compatible with CentOS, support for specific server hardware is in general excellent in CentOS. The support length of each release is also most of the time longer than the average usage period of a server. If you don't want too much headaches in the future, CentOS is therefore a save choice.

Fedora changes too fast to use on a server - its very rarely that you need the cutting edge OS on a server so there is little reason to put up with the pain of more frequent upgrades.

If you use Ubuntu on a server I would definitely use an LTS as lammert advises.

I think you should also consider Debian - Ubuntu is based on Debian so Ubuntu and Debian servers are VERY similar. I would say that it is another safe choice like CentOS.

Ubuntu is very user friendly as a desktop, but they are all about equally easy to use as servers. I use Ubuntu on the desktop and Debian on servers.

I'm in the process of installing Mint Maya 13 LTS as a VPS under Windows 8 Hyper-V. Took me a while to get things going but that was me being unfamiliar with a too-complicated Windows OS.

I moved to Mint from Ubuntu when I tried to run an upgrade of Ubuntu (12.04) and found it too messy as a desktop. Mint is a cleaner interface. The current LTS (v13) runs (I think) until 1917. It's based on Ubuntu and much of the repository is Ubuntu Precise Pangolin.

I'm using Mint to run postfix/dovecot/MySQL on a stand-alone machine as my backup mail server and it works fine, which is why I am about to duplicate this under Windows Hyper-V to replace my primary Windows mail servers.

If you want a rock-solid, real Unix-like system, use FreeBSD.

Avoid GoDaddy like the plague.

A dedicated server is too expensive and you don't need it.

@dstiles, as far as I know the difference between Mint and the corresponding Linux version is entirely in the desktop, so surely a server install will be identical?

Not sure what you mean by "corresponding Linux version".

I run the standard Mint Maya install for everything. I'm not even sure there IS a server version, though I know there is a Ubuntu server version (I tried it on the VPS to try to avoid a problem in VPS install but ripped it out again). Mint is sufficiently small that unless you are really adept at running gui-less servers I think this is a good solution. I prefer Mate but there is a choice of front ends.