Storage box from hetzner is great. Hetzner is a good company, I'm glad that I'm doing business with them. The service is good, cheap, reliable, and... Un-american which means it would probably stay good and won't enshitify.
Use Hetzner! I'm not affiliated just a happy customer.
Hard to make a particular recommendation as backing up to the cloud is a popular option but depends on your upload speed and rate of data change. And depends how much you're willing to spend for what tradeoff