((bsdiff is massivly elite:), other than that)
I personally like vbindiff (SUA mode) for small files and I've beta-tested this tool blockwatch (Windows WPF, free client, cost for network feed), which can do very fast sub-section matching over large content search space's, should be released soon.
If you are diffing (native) executables, PatchDiff2 (tool is free, IDA is$) is an IDA plugin that will get you over 90-95% accuracey no problem, even with variation's in optimization or other build settings.
BinNavi, ($) is another tool which does quite well.
If you want to qualify the similarity of binaries, STAN (works in SUA mode), can cut through the perverial B.S. quickly to get you a safe bet.
Just for completeness sakes, related to bsdiff is Google's new algorythem for their Chrome browser, Courgette seems to have improved bsdiff by a fair amount, it will be nice to see how well it can be adapted to other formats, it seems to hevially leverage an optimized symbol table lookup and what seems to be (have not read the code) an improvement you would get from using based pointers (i.e. not useing liniear addresses, but simply using the offset in as compat a notation as possiable).