How do I create binary patches?

What's the best way to go about making a patch for a binary file?

I want it to be simple for users to apply (a simple patch application would be nice). Running diff on the file just gives Binary files [...] differ.

Solution

Check out bsdiff and bspatch (website, manpage, paper, GitHub fork).

To install this tool:

Windows: Download and extract this package. You will also need a copy of bzip2.exe in PATH; download that from the "Binaries" link here.
macOS: Install Homebrew and use it to install bsdiff.
Linux: Use your package manager to install bsdiff.