You can have either Windows or Linux based VPSs. Check about the pricing for Microsoft OS before you place order with any host. If you confirm your server requirements i can help you with server selection
The OS choice would mostly depend on the host rather than on the actual possibilities. As stated earlier, most host offer CentOS 5 by default (it allows cPanel install)
What are you looking for? CentOS 5 is the most common but it all depends on your needs and your hosts preference. If you are looknig for a certain OS, then post it and you will get recommendations based on that.
It depends on the virtualization platform of the hosting provider. If they use openVZ then you are limited to Linux or BSD. you would need Xen, KVM or vmware to run windows server, linux, BSD.
Almost every Linux Flavor and Windows can be installed inside virtualized environment, but not all hosting companies offer all choice of OS, ask the provider in advance to make sure they offer the OS you want to use.