on the redhat site, as you said, is a link to fedora core and the last freely available distro, redhat9 is also still available.
both are very recomandable and well documented (get the rh9 books in pdf), also available on the redhat site, just dont stop after three clicks!
its the best bet to get you started, as things arepretty stable and relative ease of use is given. but make sure to read the docs or any other books a unix/linux at your local public-libary, where there must be books including whole distros, like the redhat9 one.
once your confortable with it, try other distros and find one for your taste.
after half a dozen flavors of linux and BSD I actually went back to redhat9 and just customized it to my needs with the 2.6.5 kernel, etc.it is very stable and functionality guaranteed.