Our application is written in Java which is a compatibility nightmare on Linux. There are half a dozen alternative Java implementations which are all slow and broken but that doesn't stop the important Linux distributions from preferring them strongly over the Sun JRE.
This forced us to bundle the Sun JRE with our application on Linux, which effectively doubled the size of it. It was worth it though because we haven't seen any Linux incompatibility issues yet.
What's the current legal status of bundling the JRE with your application? I seem to recall that fairly recently (three or four years ago) you had to download it from Sun and "sign" a clickwrap agreement in order to get it working.
This forced us to bundle the Sun JRE with our application on Linux, which effectively doubled the size of it. It was worth it though because we haven't seen any Linux incompatibility issues yet.
(ps: I can test tarsnap on ArchLinux)