Random Musings(TM):

Red Hat is good to know because it is arguably the most "corporate friendly" distro. This is an advantage if you want to seek employment is a linux-rich environment. Red Hat has a for-pay update service vs. Debian's apt system, but I've always just munged Red Hat's website with...wait for it...Perl and auto-updated that way.

Slackware - The Forgotten Distro. My favorite. Simple and solid. Slack is as close to BSD as you can get while still stamping "Linux" on the CD. Slack takes the approach that you're going to be using the command line anyway, so why muck things up with buggy GUIs.

BSD. Run one for week and you'll see why the BSD folks think linux users are lame. Install OpenBSD now, try it, if you don't like it fdisk it away.

Regarding you question on fresh install vs. upgrade from 5.2: Upgrading will have you chasing dependencies for days. Wipe it and start fresh.

A parting link: Linux From Scratch. Build your own!

Update: Bah! scottstef beat me to it! Linux from scratch really does rock.