You might be better of asking on a hosting specific forum like www.webhostingtalk.com and its ilk (there are a few out there).
In terms of "something that can handle Perl/PHP" you will need to be a lot more specific in your question than that to get useful answers. What sort of code will you be running? Are databases needed? How much data are you expecting? How many concurrent users? ... ?
For "admin user control of library/module installation", most VPSs (all cheap ones) are unmanaged which means not only that you can do everything yourself you have to do everything (beyond the initial OS installation) yourself. You need to provide in your question details of your level of relevant experience.
For a dual setup you would need to find a host that offers both Widnows and Linux VMs and rent one of each. If it is important that the two VMs can talk to each other efficiently (if they need to, i.e. one stores a database accessed by the other) you need to confirm with the provider they they will both be in the same facility. Also, you would need to check if traffic between the two counts against any bandwidth quotas or not (usually such traffic will count against your quota unless explicitly stated otherwise).