I cut my teeth on Red Hat 5.2, it's definitely one of the better RH versions, later versions got steadily crappier after that. It wasn't exactly hard either, just different (Like Linux in general really, the rewards are there but you just have to be willing to put the time and effort in to find them).
I'd be surprised if you were able to find a legal source of RH Enterprise for free, as RH are positioning it as their sole Linux product now (the desktop distro has been handed over to a third party project and re-christened Fedora) and are currently asking a fair amount of money for it ($1500-2100 here in Oz, whatever that is in your money). Even if you do, it's probably overkill (unless the dual Opteron box in question is actually a server and not a workstation). Gentoo's still probably your best bet if you're looking for a no-nonsense distro for that kind of hardware.