As a followup to apt-rsync and analysis, I should point out that the people on IRC who suggested it was already done were clearly right. What's not clear, however, is how this might enter Ubuntu or Debian accepted practice. There's been a lot of debate since apt-sync's work over other ways of compressing packages. LZMA, already seen once on this blog, is a frequent contender. Hardy allows LZMA packaging, and I've seen several mailing list threads about it. Unfortunately LZMA and rsync are mortal enemies, shall we say. I'm not sure, but I think that LZMA has won because zsync makes the CD image size problem worse, not better.
An alternative compromise might be to investigate LZMA & squashfs. Currently this represents one of the interesting problems with the Linux kernel. Almost everyone uses squashfs, and while Greg KH can go around declaring that everyone should want their code in the tree and how there's throngs of developers eager to make it happen, the LKML was fairly clear about rejecting inclusion in 2005. There's been some very recent efforts to bring squashfs into mainline, so there is hope. The trouble for squashfs- lzma is that the squashfs maintainer refuses the patches because he's afraid to risk being turned down by LKML again. So squashfs-lzma is distributed as a patch to a patch, and most distros are wary, if they're even thinking about it at all.
But assuming we could use LZMA on squashfs, that would leave Ubuntu more free to ship packages built with an zsyncable package archive, but would still leave a conflict between network bandwidth and disk space.