I don't know or care about a GUI (pssh), but you can find the original xdelta program in many Linux distributions.
Such as Debian:
$ apt-cache show xdelta
Maintainer: LaMont Jones <email@example.com>
Depends: libc6 (>= 2.2.5), libglib2.0-0 (>= 2.16.0), libxdelta2 (>= 1.1.3), zlib1g (>= 1:1.1.4)
Description-en: A diff utility which works with binary files
Xdelta is an application program designed to compute changes between
files. These changes (deltas) are similar to the output of the
"diff" program in that they may be used to store and transmit only the
changes between files. However, unlike diff, the output of Xdelta is
not expressed in a human-readable format--Xdelta can also apply
these deltas to a copy of the original file. Xdelta uses a fast,
linear algorithm and performs well on both binary and text files.
Tag: devel::rcs, implemented-in::c, interface::commandline, role::program,
scope::utility, use::synchronizing, works-with::file