I would definitely recommend Linux Mint. With Mint 16 they have made Cinnamon a complete DE (Desktop Environment), so it is separate from Gnome or KDE (And IMO, MUCH better!).
But like others have said...make a few live CD/DVD/USBs and try a few different distros out (starting with Mint and Ubuntu).
Welcome to the world of Linux!!