Какой хеш лучше получать у файла?

Для больших файлов считайте хеш не всего файла, а, например, начального мегабайта или хитрой последовательностью - десять кусков по мегабайт из разных частей файла. Всё равно если у вас подозрение на дубликат, то нужно перепроверять другим хешем или непосредственным сравнением.

Какие файлы? Универсальное решение будет, или работающее с конкретным типом данных?

Имеет смысл знать хэш файла, посчитанный, например, через каждый десяток мегабайт. Тогда сравнение можно делать частично.

Посмотрите алгоритмы, которые использует rsync.

КО намекает что быстрее MD5 только CRC32. Кроме шуток с двадцатью гигабайтами, быстро ничего работать не будет, просто потому что эти гигабайты надо через память прогнать. Такие задачи решаются разбиением исходного объёма данных на блоки. Например, брать хэш сумму каждого мегабайта, а потом общую хэш сумму полученных сумм. Достоинство такого подхода в том, что можно считать хэш у частично закаченного файла или считать в несколько потоков.

djb2, например. В сочетании с техниками, перечисленными ранее.
Взят из списка некриптографических хеш-функций