Где лучше всего хранить файлы различного размера?
развернуть собственный сервер-хранилище (эта идея была практически сразу откинута)
Не совсем ясно, отбросили ли вы исключительно "железный" отдельный сервер, или в т.ч. и виртуальные. 
В любом случае - один из вариантов - это "storage VPS", что-то наподобие вот этого (по ссылке просто пример): https://hosthatch.com/storage-vps

Также можете использовать предназначенные для хранения сервисы:
 -- https://www.hetzner.com/storage/storage-box (ФТП и подобное);
 -- https://www.hetzner.com/storage/storage-share (NextCloud).

Последние два варианта по цене побить, наверное, можно, но полагаю, что немногие из известных игроков предложат дешевле (хотя не проверял). Это уже готовые решения, которые вполне себе дёшевы и сердиты.
А среди облачных хранилищ рассматривали вариант с S3-совместимыми хранилищами, кои имеются в России и не только? У них ведь другие цены. Кроме AWS есть и другие игроки. Есть Oracle Cloud, Google Cloud, Azure Blob storage и прочие. Плюс ко всему, есть множество решений по CDN.
В дополнение ко всему, с точки зрения модели бизнеса вы можете разделить на хранение небольшого размера файлов и большого, где можно подобрать какое-то особое решение.