The python interpreter itself isn't really big when compiled into an executable. I used the freeze tool earlier (http://wiki.python.org/moin/Freeze) and it's pretty straightforward, and the result is truly stand-alone, and very convenient to deploy.

I spent the last hour or so trying to get PyQt and friends compiled/installed in a virtualenv, and this seems to be a nightmare. After this I am convinced that any user-friendly distributions should include it as compiled into the frozen bytecode.