We use Debian, but we've used CentOS, Fedora and FreeBSD in the past. CentOS is great if you like RedHat style tools (rpm's).
Fedora was great for test servers but proved to be a pain on production machines. Its changing too quickly and its clearly meant to herd corporate users to their commercial RedHat products.
All linux systems are 99.5% identical but the management tools differ slightly. FreeBSD was great but just too much of a headache to administer. Wonderful performance on FreeBSD though.
Debian is the easiest to admin and update (IMO), but has the steepest learning curve of any Linux. Well worth it though.
Ubuntu server is very popular nowadays but I've never used it personally. That may prove to be the best of both worlds, easy and foolproof.