Slicehost e Linode são dois serviços que eu já vi muitos bons relatórios. Ambos têm taxas razoáveis e são fáceis de começar.
No entanto, antes de gastar um único centavo, eu recomendo que você baixe o VirtualBox ou VMWare Player , e comece a aprender no seu próprio PC. Conceitualmente, uma VM em execução no seu PC & uma VM em execução na máquina de outra pessoa é a mesma.
Os serviços VPS terão algumas coisas automatizadas para você, mas no que diz respeito aos aspectos de "gerenciamento do sistema", você ainda será o responsável pelo trabalho. Então, aprenda em uma VM local, quando estiver pronto, configure um VPS com o provedor escolhido e, em seguida, aplique suas habilidades / conhecimento lá.