Recommendations for Hosting Solutions (Cloud, VPS, Dedicated)

We are a Saas based startup, started using Linode 5 years ago, as we started getting more clients we hired a local company to manage our servers, they recommended us a dedicated server which they resell to us, we had not the best time with them, for example: we suffered a hardware failure twice, slow response time, offered old CentOS distributions making our app harder to configure, very slow to scale, etc... After less than a year we decided to get back to VPS servers, and gave digital ocean (which offered the same service than Linode but for 1/4 the payment at that time) a try.

Everything was excellent with DO, amazing API, cheap prices, friendly panel, acceptable support, we have one 32GB droplet, three 8GB droplets, and one 512 MB droplet.

How ever we have had very unfortunate times lately (from July 2014 to today), problems in NYC2 (https://status.digitalocean.com/) made our clients very angry and today we had another problem with one of our droplets (it did not boot because of a scheduler backlog), so we are looking for new server provider.

We offer ERP like service so it is critical for us to have the best possible up time during daytime, we don't have any problems with maintenance downtime on nights for example.

What kind of solutions or providers would you recommend?