Let me toss in my 2cp worth here
Fedora is what Red Hat uses as their "bleeding edge" testing ground, so it's not near as stable as Red Hat Enterprise, and has a much shorter release time frame. As others have said, don't use it for a server OS.
CentOS is Red Hat Enterprise repackaged to be free, so if you like Red Hat, that's the way to go.
Personally, I like Debian, so I'll put in a nod for that. Debian is what powers many other distro's out there including Ubuntu. I have been using Debian on my servers and it's not only rock solid, but updates and any security fixes are taken care of right away, and they have a long release cycle so you don't have to worry about OS upgrades all the time, and you get support for what you are running for a long time.
As for CMS's, if you like DotNetNuke, the check out PostNuke on the *nix side. Both are based on PHPNuke which started out a looong time ago, it's just that with these others, you get the features without all the bugs and security holes!
As for hosting options, I'd like to mention ServerBeach. I know you have mentioned going the VPS route, but with ServerBeach you can lease a dedicated server for under a hundred bucks a month. That's for a low powered server, but one that gets the job done depending on just what you want to do with it, and how many sites you want to host. If you catch a special, you can get some even better deals too. I have been a customer there for eight or nine years now and have had literally perfect service with this company. They started off as part of Rackspace, but got spunoff and sold to Peer1. All in all they are a great company to deal with, with good prices and great support. The servers they lease are "un-managed", which means it's a do it yourself gig, but for me, that's just what I wanted.
If you need any help, or have any questions, don't hesitate to send me a private message or reply here, and I'll be glad to help in any way I can.
Hope this helps, thanks!
Laz