I'm kind of new to this as well, but I'd tried some different flavors of Linux.
First off, I have to say... once you use it, you never go back to Windows. I keep a Win machine around for games and... games. That's it.
Redhat: Pretty k00l, but it's got security holes a mile wide. It's super easy to use, install & upgrade though (with some quirks. You can't upgrade RPM, and that'll limit some of the packets you can install). If you choose Redhat (and I'd even recommend it, for a first time user) then spend a few days researching plugging those holes.
Slackware: Personal favorite. It's NOT as easy as Redhat, but it's very, very easy to modify and it's holes are not nearly so numerous, large or difficult to plug. Default install is pretty secure. I did have a problem with X 'n Slack, but I'm pretty sure that was my comp, not the OS.
Your own kernal: Very cool. You can compile your own linux kernal... you won't have all the little programs a distro will give you, but you'll be pretty secure. You'll also learn about how the OS is constructed, the dependancies, etc, etc. You can get instructions at
www.linuxfromscratch.org I think the address is.
Helix