[...]
I've only come up with one possible sollution to this. Which is, push the byte-compiling of the code into a post-install script. This way the byte-compiling can be done on the target machine. But maybe there is a better sollution?
This is the standard solution used by our own binary distributions.
What do the debian packages of e.g. Emacs do? Byte-compile at compile or install time?
One caveat about byte-compiled modules in the context of separating them into separate packages: If a package A optionally depends on a package B, it will be at the time when A is byte-compiled that it is determined if B is available. So, if the byte-compilation takes place at compile time, when all modules are available (which are supported on the platform, of course), the byte-compiled A module will not be usable without B. On the other hand, if the module is byte-compiled on install, it becomes necessary to install B before A, otherwise A will not be able to use B even though it is installed.