Andrew, also take a look at Autopackage. These guys have been doing lots of research about all issues concerning distributable linux binaries, and what's great is they're producing lots of documentation, not to mention some nice tools to make your life easier.

In this tutorial, you can find a chapter about binary portability.

And for crazy/interesting thoughts about software deployment in general, read this "dream" Mike Hearn had of having some kind of linux desktop platform.