tar+gzip performed similarly well (1.6MB -> 450kB) and is a lot faster than normal zip. GZip was similarly able to compress my Mac's System folder from four gigabytes to two. Anyway, the point stands that executable files are quite compressible. If you'd like me to try it with an algorithm you consider more appropriate, please direct me to the download page.
