I've tried Slackware, Red Hat, Fedora, Debian, Mandrake, Knoppix, Suse, and Gentoo (that I can remember). In my book Linux is the hands down winner for servers, and it has every bit of potential to blow up the desktop market if somebody would come along with some money and do it right.

I would personally try Mandrake for a beginner.