I found that distros that use LiveCD's that run the OS itself are better that regular installer CDs because they are faster. The Ubuntu LiveCD is really nice because you can fix GRUB, download patches, and partition the boot partition without consequence (Unless you do something stupid). They also tend to be much smaller and therefore easier to download. Whereas in an installer DVDs, you have to download five CDs worth of ISOs. Ouch!
Whatever you go with, I tend to stick with LiveCDs whenever possible.
A side note: Most the differences in distros come in their package installers. Some, like Red Hat's (when I used it) tend to be a pain, and you have to download every package separately. YUM didn't exist back then. Debian/Ubuntu work great, just a sudo apt-get install packagename away. Most software can be converted from distro to distro (Think Alien), so installers are the only difference. The look and feel are all on http://www.gnome-look.org/ and http://www.kde-look.org/, so Look and Feel is the same. Compiz Fusion/XGL: Ditto.
What do you think?