Tarsnap gives deduplication, compression, and encryption. Some technical background on how it does this here: http://www.tarsnap.com/efficiency.html

There is a detailed breakdown provided as well. Sample output:

                                         Total size  Compressed size
  All archives                               697 MB           323 MB
    (unique data)                            215 MB           100 MB
  This archive                               148 MB            67 MB
  New data                                    17 MB           5.2 MB

Edit: Don't want to misrepresent Tarsnap's granularity. The print-stats option gives size in bytes. Above output was generated with the --humanize-numbers option.