I currently have VM's of four Linux Distros. I have Ubuntu, Kubuntu, OpenSuSE, and CentOS.
I can't comment on the new UI in Ubuntu 11.04 because it doesn't want to run with VMWare's graphics drivers, but the 'classic' GNOME interface works as well as it always has.
Ubuntu is a pretty solid performer, as is Kubuntu because it's basically Ubuntu with the KDE shell.
CentOS always feels a bit primitive to me, but simplicity isn't always a bad thing.
OpenSuSE (SuSE is developed by Novell, OpenSuSE is the free version) gives you the option to install either GNOME or KDE. I installed KDE, so it feels like Kubuntu. OpenSuSE is by far the quickest of these four Distros to issue software updates, CentOS is the slowest. It seems like OpenSuSE has an update every other day.
I would suggest before deciding to jump in with Ubuntu, to try as many Distros as possible. Of course, being Linux based, they're all going to operate more or less the same way. I would just steer away from any builds (Such as Puppy Linux) that run user accounts as ROOT, as this strips away the main reason Linux is generally more secure than Windows. Linux is less of a target to malware authors because the vast majority of Linux users are running restricted user accounts, and for malware to do any real damage, ROOT access is needed. As such, it's incredibly difficult to become infected without the users help.
You asked about installing software. Depending on the Distro you pick, the software you want to install my already be listed on one of the repositories. In that case, all you need to do is open the Program Manager and do a search for that application. If it's listed, you just tell it to install and the OS does the rest. Otherwise, DEB or RPM's are generally as easy to install as double-clicking on the file, if it's a TAR, you're going to have a bit more involved installation that will vary depending on what Distro you're using.
This is a pretty useful starting point in regards to installation, although it doesn't touch too much on specifics of the various Distros.
How To Install Software in Linux - Linux Forums