Сравнение больших нетекстовых файлов

Как отметили в комментариях, побайтовое сравнение будет самым быстрым (если все байты в памяти, конечно - впрочем, в C# реализовать обратное надо ещё умудриться).

Но для начала файлы можно просто сравнить по размеру. Если он разный - очевидно, файлы отличаются.

Если размеры идентичны, и нужно всё же сравнивать побайтово, файлы можно разбить на куски, и запустить сравнение в параллельном режиме.

Приведу код с примером такого сравнения. Код не идеальный и не универсальный, но вы сможет от него оттолкнуться

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading.Tasks;
namespace FileCompare
{
    class Program
    {
        static void Main(string[] args)
        {
            //Считываем файлы в память
            var file1 = File.ReadAllBytes("file1.bin"); //10 000 000 байт
            var file2 = File.ReadAllBytes("file2.bin"); //10 000 000 байт
            var partsCount = 10; //количество частей
            var partSize = 1000000; //размер части
            //делим файлы на списки частей
            var parts1 = new List<IEnumerable<byte>>();
            var parts2 = new List<IEnumerable<byte>>();
            for (int i = 0; i < partsCount; i++)
            {
                var skip =  i * partSize;
                parts1.Add(file1.Skip(skip).Take(partSize));
                parts2.Add(file2.Skip(skip).Take(partSize));
            }
            //Создаём список тасков. Метод Task.Run запускает задачу сразу после создания
            //Так же обратите внимание на current = i в каждой итерации.
            var comparsionTasks = new Task<bool>[partsCount];
            for (int i = 0; i < partsCount; i++)
            {
                var current = i;
                comparsionTasks[current] = Task.Run(()=> 
                {
                    Console.WriteLine($"Running {current}...");
                    return parts1[current].SequenceEqual(parts2[current]);
                });
            }
            //ожидаем завершения всех задач
            Task.WaitAll(comparsionTasks);
            //вывод результатов в консоль
            foreach (var task in comparsionTasks)
                Console.WriteLine(task.Result);
            Console.ReadKey();
        }
    }
}

Кстати, учтите, что для небольших файлов это решение только замедлит сравнение. Тут только замерять.

И ещё: можно использовать CancellationToken для того, чтобы останавливать сравнение как только обнаружены разные байты.