Thanks for the random access discussion!
And you are right for embedded! .xz just doesn't work there.
I've also found that on the faster systems, for different uses of mine, when I want the compression to last as little as possible and the total round trip time matters (compression and decompression), gzip -1 gives the best resulting size for the reasonably short time I want to spend.