When it comes to running in the "cloud", I'd probably go for Hetzner. Way way way cheaper than the examples mentioned in this post. I guess the main question is, how much is privacy really worth to you - or what other alternatives are there that meet my demands ie. Mapbox?
Think I'll give this a go, always have wanted to run my own instance of OSM, to see how performant it is/how much traffic you can handle on a single server.