Eu tenho experiência pessoal com o Slicehost. Eles foram adquiridos pela Rackspace há algum tempo. Na minha experiência e em todas as pessoas que ouvi mencionar, a Rackspace é profissional e confiável. Eu também posso recomendar o linode.com. Tenha cuidado com o que você escolher, porque existem muitos provedores horríveis de VPS por aí.
A maior razão pela qual eu amo VPSes é que eles são facilmente ajustados às suas necessidades. Então, se eu tiver uma explosão de tráfego, por exemplo get slashdotted, eu posso ter uma máquina 10 vezes maior em um período muito curto, a qualquer hora do dia. E, se eu fizer downgrade dois dias depois, porque o tráfego está de volta aos níveis normais, muitos provedores de VPS só cobram o servidor grande por dois dias. Para o Rackspace Cloud, acho que é mesmo por hora ou por minuto.
Com hardware físico, as atualizações são difíceis e demoradas. Então, a menos que suas exigências sejam muito extremas, eu sempre recomendaria um VPS.