I do not recommend the Fedora series at all.
Fedora has its advantages, and certainly are cutting edge as far as revisions of major applications (apache is in the 2.2 branch, MySQL is using 5.0, and PHP is in the 5.1 branch for the newest Fedora) as well as kernels (which will allow you to use newer hardware).
The biggest detractor in my eyes is the lack of extended support, with versions being phased out ever 6 months, that is a pretty heavy revision cycle. With the additional support of the FedoraLegacy group (which is great btw), you still can not be assured that your server will remain up to date for as long as it is in production. I personally have a RedHat 7.3 server that is still in production, and I am lucky that updates are still provided due to the large user base for this distro. Other distros have not been so lucky (read: RH 8.0). This factor alone makes me very leary of using Fedora.
My recommendation (opinion) would be to use a distro with a long development cycle as well as an established and relatively smooth upgrade path.
Specifically I am referring to Debian. Debian stable is regularlly updated (with security patches), and has a well established in-place upgrade system (via apt-get dist-upgrade). I know that Fedora has something similar, but my results having used it in the past are poor in comparison to the Debian results.
Debian isn't perfect, as the stability comes at the price of a lack of available upgrades to more cutting edge applications (for instance there is no PHP5 in Debian stable). You can add these to Debian via backports, but they are not officially supported by the Debian maintainers, so you are kind of on your own there. Additionally Debian's kernel is a little out of date (2.6.8 for the 2.6 branch) so if you are installing it on to newer servers (specifically most newer PCIe based boards) you will encounter some issues with unsupported IDE/SATA chipsets, as well as network interfaces.
Also Debian does things differently than RH (Fedora/RHEL/CentOS), so there might be a learning curve that you need to adapt to, so that might also influence your decision (things like config file locations; default run levels, which is 2 on Debian and 3 on RH; etc).
My limited experience with CentOS prevents me from commenting to much on it, however with it being tied to the established (and heavily supported) RHEL line, I think that it is safe to say that going with CentOS would avoid the pitfalls that I mentioned earlier with Fedora.
Either way, Debian or CentOS would be my choices.
As a bit of background I have a total of 7 Plesk servers that I manage ranging from versions 5.0.5 to 8.0.1. the last 3out of 4 I have installed have all been Debian 3.1 (the other one was Windows 2003, so it doesn't count

).
I hope that gives you some information on which to make an informed decision