Well I'm a Linux n00b too, and I've tried Mandrake 9 and Redhat 8 so far. Didn't get very far with Mandrake 9, because for some reason it refused to work with DHCP, so I can't tell you much about it; but Redhat 8 was a great experience. A little hard to get everything tweaked the way I wanted to because it doesn't include much in the way of multimedia, but for office apps and such it's a great distro.
From what I've read, SUSE 8.1 is a sweet distro for beginners and experienced users alike. If I re-install Linux again, it'll be SUSE.