OK, I figured it out!!!
This should be added to the rooting guide to help users with Macs that want to use a Windows VM. Mods, can you help here?
Basically, the KEY to the whole thing is that for Caroline to see fastboot, is that you have to toggle VirtualBox's USB controller off and then back on... I had to do it twice.
Do this by going to the top menu bar in VirtualBox, selecting Devices->USB Devices->usb, Android 
toggle it once, wait a second, then boom Caroline does her thing and says something about rebooting once Moar
toggle it again, wait a second, then boom it asks if you want to download and install Recovery.
In the Mac via Virtualbox with Ubunu guide (http://forum.xda-developers.com/show....php?t=1199725
) it alludes that you need to toggle the USB off and back on, but he tells you how to do it through the OS. You can get root via rEVOlutionary in any Windows version running on VirtualBox (I'd guess) by toggling USB through the VirtualBox top menu.
I really hope this helps others.