I've been quite happy with Delimiter [1]. Cheap, but relatively beefy dedicated servers and S3-compatible object storage. You can use promo code B6NFT66YU7ZN to get 6% off in perpetuity (disclaimer: that's my affiliate code).
They are literally the worst hosting business I've ever dealt with, and I've used many of the low-end providers. OVH and online.net are miles better.