Running Linux off of a CD or DVD is a nice, quick means to play with Linux. While I have not used a VMWare virtual machine, the "player" is free.
I am running SuSE 10.2 on a dedicated machine (KDE) and decided to give Microsoft's free Virtual PC 2007 a try with an Ubuntu 7.04 (Gnome) installation. Note, you do not have to burn a CD or DVD, VPC 2007 can load from the ISO image. I also compiled source for Mono and MonoDevelop, among other things using this environment.
VPC 2007 provides the network interface, sound, and PS/2 support. Sound is limited to a Sound Blaster PCI card and graphics are limited to 16-bit color. Ubuntu (and probably most distros with a GUI interface), defaults to 24-bit color. As a result, as part of your set up, you do need to understand how to change the color depth from 24-bit to 16-bit. You also need to add an entry to the Grub loader to get mouse support. I know you're new to Linux but neither of these items is a big deal if you follow the instructions here:
This link is for SuSE:
SuSE needs to fix its sound so it will work with VPC 2007.
I noticed that the Ubuntu install was fairly fast for the VPC 2007 installation, while the SuSE 10.2 install was very slow (far slower than my dedicated machine's install). However, once things are installed, the speed is reasonable. I did notice keys being repeated but going to the keyboard settings and modifying the configuration handled that issue.
If arcade gaming is of interest to you, you should not look at any of the virtualized hardware offerings but set up a dedicated machine with the right hardware.
If learning Linux is your goal and you'd like to have it running side-by-side with your WinXP Pro or Vista installation, either VMWare or VPC 2007 are worth a try.
Finally, if your hardware contains virtualization support, make sure it is enabled in your BIOS and make sure you check the VPC 2007 setting to enable hardware virtualization.
Good luck and, above all, have fun!