[...]
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.
Is there a way to avoid byte-compiling at compile time that I've missed or do you just discard the .o files?
What do the debian packages of e.g. Emacs do? Byte-compile at compile or install time?
At install time.