I'm running a new install of Plesk 8 on Fedora 4 and I am generally quite happy. I can't see what all the fuss about Plesk 8 is - that's probably because I did a clean install, not an upgrade from another version. Sure, there are some problems, but nothing major. (Out of curiosity has anyone had trouble with a new install of version 8?)
I was considering CentOS (or even subscribing to Red Hat Enterprise) but in the end it came down to Fedora 4 having the later versions of those packages I chose to care about (PHP, MySQL, PostgreSQL). Anyway, what I did was a "server" install of Fedora 4 selecting relevant packages (Web server, MySQL server, PostgreSQL server etc. - don't select FTP server because Plesk installs its own).
You'll also need to make sure some SELinux packages are installed (type yum install selinux-policy-targeted selinux-policy-targeted-sources selinux-policy-strict selinux-policy-strict-sources) to avoid version incompatibilities with the Plesk-supplied packages. Then run yum update to get the latest updates for the system.
Then follow the Plesk install instructions for the autoinstaller.