feedback is very much needed
Cheapest is to stay away from anything related to the big clouds, especially Amazon with their "premium bandwidth" charges.
I'd probably spin up a storage box from Hetzner (or similar service for dedicated servers) as a first step, as you get unmetered connection. It should last you a pretty long while as most content will be fetched from caches.