Either Ubuntu or Kubuntu will do. I've used both. the 8.04 release is pretty stable now, its point release having come out in the late Spring/early Summer. You can download it from
http://www.ubuntu.com/getubuntu/download.
You will get equally excellent advice from what is certain to be a long line of responders to this question. Stating what you want to do with Linux will help responders out quite a bit.
I do database development, and, if I had it to do over, I'd install Ubuntu server, and then add the desktop. The reason for that is Kubuntu, Ubuntu, and Xubuntu are desktop clients by default, but are easily made into servers by adding the rest of what's needed like build-essential and apache. Ubuntu server comes with all that but not the desktop.
Some people say Kubuntu is more like Windows, while Ubuntu is more like a mac. I happen to like Kubuntu, but cannot tell you why. Perhaps the menu customization might have something to do with it. Also, I like the Ubuntu community, but, then again, the LQ community is pretty good, too.
As to upgrades, I have found Ubuntu very easy to upgrade things on like the Informix module for Perl and SOAP::Lite versus Red Hat Enterprise Linux. You should also note Ubuntu is Debian based, while other distros are rpm/Red Hat based. I like aspects of both major distros.
If you are starting out with Linux, I'd stay away from things like Fedora, although I like the distro a lot, only because its download support runs out after a little over a year, and you'll have to upgrade. Unless you like building Linux boxes, I'd find something like CentOS or Ubuntu LTS releases that give you regular updates and some breathing room, before you have to update a system.
Brian Ward's How Linux Works is an excellent book, and you would do well to purchase a copy and read it.
Happy Linux-ing.