Glandium brought this up in bug 1291424, and I think it's worth looking into. With a local build (with debug symbols), my szip-compressed libxul is 27M. With xz and default settings it's 19M (and also the same with 'extreme' settings too, strangely enough). An 8MB savings is pretty awesome. We would need check to see if the libxul on disk is different than the one in the APK on every startup, and then decompress it if necessary. Nick Alexander had a good idea to use the CRC out of the APK to do this quickly, but it might be good enough to just see if the sizes match.
I tried this for the libxul in the Firefox 48 release: original (szip): 18M pixz: 13M So it looks like we can chop 5MB off the APK size by doing this. That's enough to take the libicu stuff (bug 1215247) and have room to spare!