gzip --rsyncable does make gzip set boundaries so one change doesn't affect the entire rest of the file, just one block.

However, the resulting differences don't seem nearly as amenable to the bsdiff algorithm as the changes to the underlying uncompressed data. In almost all cases, you'll likely get better results with bsdiff on the uncompressed data (and bsdiff internally compresses its result).