Since I develop backup software, this is a problem I needed to solve (e.g., for verifying that restore works). So I wrote a tool: http://liw.fi/summain/
It produces output that is meant to be usefully diffable.
That's a neat looking application - bonus points for a good manpage, too.
That said, how does it handle firstpath/somefile.bin and secondpath/somefile.bin being identical? This breaks your "diffable" output because the paths are different.
It produces output that is meant to be usefully diffable.