I've found, building Python binaries for Windows, the interpreter and standard library takes up a negligible amount of space (a few MB). Most of the space was taken up by dependencies anyway, e.g. wxPython something like 15 MB! (I think I got it down to 7 MB using UPX to compress the DLLs.)
UPX is not magic -- it compresses machine code and makes sure unpacking code is run every time the executable is loaded. So if you only care about the size of the binaries in transit, don't use UPX, just use eg NSIS with lzma compression. You'll probably end up with a smaller package this way.
