Two comments:
Some portion of your concern is being addressed by the content-addressable effort. It’s granularity is at the package level, but it may help short-circuit the required builds.
Storage mechanism and cache:
I’ve thought it would be interesting to have a GitHub - systemd/casync: Content-Addressable Data Synchronization Tool based store (or cache). It would perform deduplication at a much more granular level, making sync up to the cache as well as download much faster. It would still use S3 and narinfo, but each nar would be a caidx file pointing to all the blobs needed. I’m not sure how much work it would be to wrap the existing S3 store for this, but I wouldn’t mind trying if someone can point me in the right direction.
Some discussion: git tree object as alternative to NAR · Issue #1006 · NixOS/nix · GitHub