Debian has its down falls but I agree it is a pretty solid OS. But try using a package that is not designed for debian or doesn't meet it's strict licensing policies, like how fire fox became ice weasel.
It is a great OS though I like it as well and its great for servers because most server packages are already there for debian, and APT is a great tool as well.
For first time Linux users I recommend redhat based distros running KDE because it is the most "like windows" version of Linux I have used and makes the switch easier. Then once you learn how to work with Linux you can easily (sometimes) migrate into another distro.
Like I mentioned before hand, just get one up and running like ubuntu since it seems to get super hyped and then start installing and running virtual machines of different distros via VMware or virtual box or what not and see which one you like best, then go with it.
Some good advice there, tlarkin.
I also recommend Knoppix(as mentioned in my honorable mentions), simply because it is quite effortless, especially if you dont want to install to hdd. Knoppix will get you up and running in only a few short minutes, with KDE as well. I think Knoppix is worth exploring as well, and if you choose to install to hdd, it's very simple.
I think everyones preferences are slightly different when it comes to distros, it really comes down to what you want it for, tlarkin pointed out Debian in a server environment, and I agree completely. We run dozens of Debian servers here, and a few gentoo(I wont get into that right now
). I would say it would be best to experiment with a few of the mentioned distros on this thread and find what best suites your needs.
Good luck, whatever you choose.