I agree with your judgement on OVH and the top tier cloud providers. I've never used Hetzner but I've had good experieces with UpCloud, Vultr and Linode/Akamai. These three providers are my defacto goto everytime I need to deploy stuff...
I have been using Kimsufi servers (OVH cheap end) for more than 10 years and have not experienced any major outages (and can't remember even small ones).
I still have one dedicated server there. 14eur/mo for i5 750, 16gb ram and 2tb hdd seems quite good to me.