Make sure you use CFLAGS that limit the amount of debug data in the binaries. "-g1" in gcc should be enough to get stack traces on crashes, while reducing the binaries quite considerably compared to the default. "-g0" will give another visible reduction but removes all debug symbols, thus making it difficult to diagnose problems remotely.

Apart from that, there used to be support for stuffing the standard library into a zip file, which shrinks .py and .pyc files by a good margin. Not sure what the status of that is, though, since I never needed it.

And finally, I'm not sure if this is worth a (bug) ticket, rather than starting a discussion on python-list. Since this is a usage and deployment issue, the larger audience there might have more ideas and experience with things that might work without changing CPython for it. In any case, there will be no changes from the CPython side for this regarding Python 3.6. Anything this ticket might result in would be targeted for a future yet-to-be-released Python version.