I haven't used FC 6 yet but have used 3, 4, and 5 quite a lot. I prefer Gentoo over FC as I like the packaging system (portage) a lot better and find it generally is more stable than FC.
If you still prefer the Redhat/Fedora brand you should check out CentOS. It is essentially Redhat ES without any of the branding in it so you can download it free. I recently installed it on a new server here at work as some monitoring software I need to install requires Redhat ES. So CentOS does the trick without having to drop a couple grand on the OS.
Fedora is more of a "desktop" linux in my opinion. So I guess it really boils down to what you are gonna be using it for.
I can second the comments about CentOS. I have used it as well and it is 100% binary compatible with Redhat apart from the fact that they are required to remove any Redhat branding from the packages as well as from their website. They basically compile publically available Redhat sources after removing any branding.
I am using FC6 now and I love it. A LOT easier to install than Gentoo (imo) and it is a little more friendlier than CentOS. AGLX is built int so using Beryl is a breeze. But if you are wanting a solid system without any eye candy than CentOS 4.x by all means.
I have installed FC6. After installation, I was alerted by the OS to download and install patches and upgrades. I installed 100+ patches and upgrades as suggested by the OS alert. Now, when playing audio Cds the computer freezes. I have not been able to rectify the matter. The CDs worked fine before the upgrades.