Ubuntu's a great, easy to use and easy to setup distribution for the new user. Pretty much everything can be done via a graphical tool, although Debian might be better for the more advanced user.

My distro of choice. I use this on my desktop, laptop and server. Can be very stable (if you run lenny, which is currently stable), or cutting edge (if you run sid, which is unstable). If you just want some new software, you can also run stable (lenny) or testing (squeeze) and get packages from sid with backports. If you like Ubuntu and are quite experienced, give Debian a go!