Ubuntu is a great distro to start out with. Grub installs nicely (the boot loader, which automatically detects XP), and the package management is very automated until you get a genuine feel for what does what. Compiz is enabled by default (eye candy). You can also find a tutorial for just about anything on the forums as well.
There are two MAJOR choices in desktop environments, Gnome and KDE. Gnome comes in Ubuntu and is set up like a Mac (with the drop down menus at the top, etc.); KDE has one main menu in the lower left hand corner, similar to the Windows START menu. kUbuntu is the EXACT SAME piece of software, but comes prepackaged with KDE.
Sabayon Linux is an extremely progressive distro based on Gentoo. The live DVD comes with some games installed.
Good luck with your install(s).
Cedega is the name of the program you are looking for, with respect to gaming.