Is it possible to run two different VMs at once using multiple instances of Parallels (for example, running Windows in one VM and Linux in another)?
Yes. This is possible. I am, in fact, currently running a Windows XP VM and Fedora Core 5 VM. VirtueDesktops makes this even better as I have both fullscreened on different desktops.
The overall Parallels preferences are shared but the VM specific preferences are not shared. All you have to do Is right-click on the Parallels dock icon and choose "New Window". Then just choose a different VM to sart.