One reason that zips are larger than compressed tar files is that each file in the zip is individually compressed. For this reason, a zipped tar file will usually be smaller than a zip of the tar file's contents. A tar.gz or tar.bz2 is just full tar file that has been run through gzip or bzip2 compression, so cross-file compression works there.

I'm not sure how 7-zip behaves with respect to cross-file compression, but cross-file compression I would think in theory be possible without requiring all the intervening files to be decompressed in order to get to a specific file in the archive. Doing so might require a great deal more work, though, and might increase the size of the archive.

I just ran a test with zip test code I have at work, and it took around 100 msec to scan the table of contents from the 2012-03 complete.zip and store the information in a std::map. This only needs to be done once at program startup (and again any time the user changes their part library to a different one, of course).