Speaking as someone who has worked on this problem for my own projects [1], I think I can answer this.
Fedora/Yum already supports downloading a binary diff between rpm packages to reduce download size, but this also requires keeping a cache of previous rpm's to run the patch against. There are multiple reasons why you can't rely on binary diffs against the files actually stored on the system, most namely for files like /etc/* that are more than likely modified since installation.
But the real problem with binary diffs is that unless you're doing what Google does to ensure that people stay up to date, the number of binaries you need to diff against grows very quickly, and there are a lot of edge cases to take care of.
For example, let's assume some package A has been released as version 1, 2, and 3. When A has a new release 4, you obviously want to build a diff against release 3, but then you also most likely need or want to build a diff against 2 and maybe even 1 to take care of people who haven't already upgraded to 3. And even if you build a diff against every single version ever released, you will still always need to provide a full version of the package as well for two cases:
1. New installations, or reinstallations, of the package.
2. When the user has cleared their package cache to save room.
And even beyond that, creating diffs involves a lot more effort and knowledge on the part of the packaging team because they not only need to know how to build those diffs, but they also need to keep track of old package versions to build those diffs against.
The end result is that you trade download bandwidth and time on part of the server and end users for a lot of effort, time, and storage space on part of the packagers and distro mirrors. For mirrors that are already encroaching on 50GB for a single release of Ubuntu and/or Fedora, adding a whole bunch of binary diff packages will most likely grow the repository size by at least 30-50%, if not more, depending on how many old versions you diff against.
The question then becomes: does this trade off actually make sense, or does it present further roadblocks for contribution from packagers and donated mirrors?
[1]: If you would like to see how I handled this sort of task, I have a Python library I wrote to handle the client side updating. I know it's not the entire piece of the puzzle because it doesn't cover generating the updates, but it might be useful for someone else. http://github.com/overwatchmod/combine