These are all good suggestions. However, I would recommend not diving straight into Ubuntu for the simple reason that Unity has a bit of a learning curve unlike many other distros. Anything with Gnome3, such as Fedora, I would also caution against until you've gotten your feet wet a little.
I used to recommend Mint to first time users because it is close enough to Windows that Windows users pick it up very quickly. However, in my experience, Mint always has a lot of bugs and this can turn a new user off.
Recently, I started recommending Zorin OS to new users to try. It is based on Ubuntu, but the default desktop looks and feels very much like Windows 7. There is a lite version for computers that have low specs or that can not boot from a DVD or USB but can boot from a CD. This version has a default desktop that is very similar to Windows 2000.
But the best thing about Zorin OS is that it is very easy to switch themes using the Theme Looker (I think that is what they call it). You cam make the desktop theme Win7, Vista, XP, Win 2k, and even Mac OS X just by downloading a new theme. Once you have downloaded the theme, you can switch back and forth very easily to others. And, once you feel comfortable with the OS, you can try out a real Linux like theme. I can't remember if it is based on Xfce or LXDE, but either way, once your play with it and get used to it, you should have no trouble finding your way around other Linux desktops.
There are free versions and paid versions. The only difference between them is the paid version comes with a lot more software built in. However, if you choose the free version, you will have more than enough software to keep you busy for a while and anything you are lacking, you can download for free from their software center.
The forums tell me I can't post a link because I do not have 5 posts yet. If you want to check it out, just google Zorin OS and it should be the first link.