How about compressing the files while building the archive instead of compressing the entire archive itself? That ought to preserve reasonably fast reads. It won't give optimal compression but in practice should do alright (and of course will be smaller than no compression).