I like the DigitalOcean and actually AWS options. AWS does have some nice infrastructure benefits (e.g. Route53 and some of the monitoring features.) Linode is fairly popular also.
On the other hand, you could buy a $500 server, colo it for $30/ mo and have all the power you would need for some time and get much more performance. RAM ends up being the limiting factor in WP performance once it is cached properly. RAM is inexpensive for a colo'd server.
Are these already nginx + varnish + MariaDB configurations?