Virtual Machines are slow, no matter what.
Try VirtualBox. I use it all the time, and get near-native speed. "Near-native" meaning that I hardly ever notice any slow-down during normal use, and I've watched videos in the guest without any of the acceleration stuff turned on, without any problems, except in one guest. I've run it on WinXP and Ubuntu 9.10 hosts, with WinXP, Win7 RC, Ubuntu 8.10, and 9.10 as guests. Of course, it does help that I have a dual-core processor.
They require a windows license and they suck when it comes to D3D and even OpenGL. [...] eat up half your RAM just to launch a crapload of services that come in your typical Windows installation.
True. Though VB has experimental support for hardware acceleration, it hasn't worked for me, and I haven't tried to run games in a VM, except once (unsuccessfully).