Rather than using .zip, an improved APK format could be more like a tarball. You'd tar up the files, sign it, and compress the result.
To verify, you decompress (streamily, without saving the result anywhere) in a tight sandbox and verify the signature on the output. Then you decompress again to install. Call it APK v3.
This adds a second pass at decompression, but decompression is generally quite fast. In exchange, you avoid a much slower recompression step.
Yes, it definitely seems like fixing the flaws in the original APK design would be a win! Just signing the uncompressed data, as many others here have pointed out, would allow most of your suggestion to be implemented.
I wonder if it's a sign of communication problems between the Android and Google Play teams? The Play team seems to have spent years bending over backwards to build this really awkward solution, which could have been done a lot better with some low-level Android changes (i.e. a new APK format).
I bet there's a valid historical reason for the current design: APK looks a lot like JAR and Android is kind-of-sort-of Java. Java random-accesses its JARs, so the awkward format makes sense in the context. Android may, too, to a limited extent, but Android has no concept of running an APK in place, so it doesn't need this capability.
Perhaps I'm misunderstanding what you're suggesting, but IIRC installed Android apps are still compressed on disk, to save storage space, hence the recompression.
Rather than using .zip, an improved APK format could be more like a tarball. You'd tar up the files, sign it, and compress the result.
To verify, you decompress (streamily, without saving the result anywhere) in a tight sandbox and verify the signature on the output. Then you decompress again to install. Call it APK v3.
This adds a second pass at decompression, but decompression is generally quite fast. In exchange, you avoid a much slower recompression step.