CentOS is basically RHEL, which you see a lot in the corporate world. It is very stable, but doesn't have the latest packages. Debian Lenny and Etch are also extremely stable, but tend to have older packages in the repos as well.
Ubuntu tends to have better community support and newer packages and is usually very stable as well, but is more prone to instability due to their tendency to add new packages to their repos frequently (this is not a bad thing though!). Neither of them are an LTS (long-term support) version, so I would go with 9.10 if this is the route you choose. Server edition is the same as regular ubuntu, except without a GUI (which you can uninstall yourself).
Gentoo seems like the odd man out here. It certainly has its merits, especially being very slim, but you see far fewer production Gentoo servers than any of the other choices. It can be daunting to learn on Gentoo, especially since their communities are not as large as the others (once again - not a bad thing. Just something to consider)
Basically it's up to you, but if I were choosing it would be between CentOS, Ubuntu 9.10, or Debian Lenny.