Parallels, unlike VMWare, is actually quite capable of running games in a Windows virtual machine. Unfortunately, you still have to contend with OpenGL only supporting version 2.1 of the specification, while the DirectX support is all the way up to 10. Maybe they'll make higher OpenGL versions a priority in the next paid upgrade. Which doesn't help you at all, since you're planning to run Linux. It does, however, disprove that virtual machines are incapable of running high end games. I can run Borderlands 2 at a reasonable speed in the VM, (which has a Mac port that loses multiplayer compatibility with the PC version whenever there's a version desync) as well as Killing Floor. (which has a Mac port that's just plain broken. For instance, it is incapable of remembering progress of class advancement achievements, unless you actually earn the entire level and Steam achievement in one match.)
If "Anything but Windows" for your primary OS is really the general idea, consider Hackintosh or CustoMac, as it generally works on many systems. Of course, depending on your motherboard and GPU, you may have to look up whatever customizations you may need. Recommended install kit is built with myHack, and if that doesn't even boot, your machine may need something in the kernel boot parameters, like npci=0x2000 or 0x3000, or pcirootuid=1. Or if you have a recent AMD video card, you may need to enable your integrated graphics for boot, even without a monitor attached to it. Sounds like fun, doesn't it?