Подкачка файлов из интернета

Если вкратце, то:

Где хранить эти файлы?

Зависит от того, какой тип доставки файлов вы будете использовать.
Я могу сказать вам как минимум 3:

1. HTTP - Web Сервер, который по простому адресу (http://site.ru/file.dll) выдает указанный файл.
2. FTP - Примерно тоже самое, что и Web, только акцент идет больше на передачу файлов. Также ставится сервер, который по указанному адресу (ftp://server/file.dll) выдает файл.
3. P2P - Позволяет раздавать файл не с сервера, а с устройств каждого пользователя, который стоит на раздаче. Вы могли его видеть не раз в Torrent'ах. Проблема такого подхода в пользователях, ибо если нету нормального "раздающего" - нет и нормальной скорости для других.

Как реализовать их скачивание?

• Для FTP и HTTP просто скачивайте пару файлов за раз асинхронно через какой нибудь WebClient (примеров даже на SO уйма, найти думаю сможете).
• Для P2P предстоит помучатся, изучить его особенности, посмотреть какие библиотеки все еще актуальны для C# и следовать их инструкциям.

Как реализовать проверку файлов у пользователя?

Большинство подобных программ делают обычный текстовый файл, который содержит в себе информацию о каждом файле проверяемого приложения (его путь и название, размер, хэш).

Пример простого такого файла:

file1.exe|137523|00g0fdd090df
dir1/file2.txt|1343|adg07ga0ga
dir2/file3.dll|137523|ag7a8ga0a00

Тут например с каждой новой строки идет
путь и имя название некий разделяющий символ размер опять разделение некий созданный хэш этого файла (md5 и др.).
Естественно вид файла может быть любой, хоть в базу засуньте и через API передавайте.

Дальше вам надо разместить это в удобном для вас месте, которое доступно для клиентов (обычно используют Web), ну и дальше дело техники:

• Качаете этот файл и считываете его.
• Сверяете по нему все файлы клиента и составляете список всех отличаемых файлов (не тот размер, нет файла, Md5 не совпадает и др.).
• Начинаете процесс восстановления (зависит от протокола, задача проста - скачать оригинал и заменить им файл клиент).

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