Do you have a full choice of operating systems for your VPS, or are you limited to only those that work with a particular type of VPS software? Do some VPS software clash with or not work well with some of the server side software-OS and other software?

It depends on the technology. Most commercial vps software duplicates the kernel of the host machine, so if its running Linux, so must all the virtual machines under it. Same with Windows. This has the advantage of high performance, low cost.

Some technologies like VMWare allow you to run different OS's at the same time, but with low performance, high cost.

Yes, I have experienced the performance of VMWare in the past unfortunately, and would prefer not to go there again, though I understand that won't be an issue soon since it got bought out by Microsoft. However it would at least mean that if desperate, we could do a little more than we could otherwise.

Does VM or another virtual machine allow you to run *nix on a windows server?

Huh? Since when did Microsoft buy VMWare? VMWare is owned by EMC.

We use XenServer (owned by Citrix), it's got pretty much all the features of VMWare at much less cost. XenServer's Hypervisor lets you run Linux or Windows guests off the same host with no problems.