I'm not a very big fan of Red Hat.
Depending on what you want, I suggest the following:
SuSE - extremely easy to install and detects pretty much all hardware. Great to start with, I guess. If you know unix based OSes already, you might be annoyed by all the GUIs and the custom init scripts and Yast messing with the config files. If you don't want to mess with config files by hand, this is not an issue for you. Go get it.
Ubuntu - beats SuSE when it comes to package management, but it's harder to install. Personally, I hate apt-get with a passion, but that's because I hate every single package management out there.
Personally, I use Slackware, but I guess that's not a good option for starters.