I have been using Hetzner, I have few servers there. Linux and Windows. They are very cheap if you look someone in Europe. I usually recommend Hetzner and if there will be scaling problems we can always move to expensive places like AWS and Azure.

I also have great experiences with Azure but not sure how it fits to startup world. I am only working on Azure on enterprise (.NET) customers and for them it is a nice service. Microsoft has Bizpark where you can get tons of Azure power for next to nothing. https://bizspark.microsoft.com//plus/

I have not worked on Google Cloud but as mentioned in comments I probably should look into that.