Also pixz, which can use multiple threads for decompression.

I spent some time a year ago comparing formats, and ended up liking pixz the most, especially being indexable. EXCEPT that according to my notes, I couldn't find any gui archiver that worked with it. Do you know if it is still that way?

I've only used it from the command line, so I don't know. For my needs, the ability to use multiple threads for decompression was its killer feature.

lrzip :-D