Store without compression/use simpler compression method? If the main point was to reduce number of tiny files.
I thought you meant seeking to any file which is possible with lha (but not necessarily possible with lzx or any other with "solid" method without decompressing all previous files in archive). AFAIK no normal archiver supports random access seeking to any file position without (at least partially) decompressing the file first.
In my opinion some kind of caching (decompress file when needed on the fly and then keep decompressed data in memory) would fix the slow down problem. Files are generally tiny (unless slave use disk image) so decompression is always fast
