rmlint é nativo do Linux, muito rápido e oferece muitas opções para decidir qual arquivo (de cada conjunto duplicado) é o "original". Ele usa a soma de verificação SHA1 (160 bits) por padrão, mas também pode fazer comparação byte a byte.
Infelizmente, não está nos repositórios do Ubuntu / Debian, mas a instalação é bastante fácil (veja as instruções aqui ).