Very interesting. Is patience diff your tool's default algorithm? Do you support diff algorithms (perhaps for different file types) other than patience or LCS?
I've been itching to figure out how to combine perceptual hashing, computer vision like opensurf, and stable marriages to do something really interesting for image diffs, but until I can shed some less sexy responsiblities I don't think I'll get to play with that.