What are the pitfalls and workarounds when using Python virtual environments on Windows?
You might want to take a look at zc.buildout. Assuming the user has Python installed, you can double click on the bootstrap.py python script to generate the environment.
Once created, doubleclicking on bin\buildout.exe will recursively install dependencies and run any pre/post hook methods you define. zc.buildout allows you to specify platform specific dependencies and non-python dependencies. Additionally, you may define your own scripts for buildout to place into the bin\ folder. For example, the Plone team has a good article running Buildout on Windows referencing their own script bin\instance.exe
While not quite a polished as virtualenv on Mac/Linux/BSD, the same buildout environment will be created (eg. bin/buildout instead of bin\buildout.exe) achieving the cross-platform requirements you have.