Proalojamento, para mim os melhores preços, Ex: Servidor Linux, 5gb disco, tráfego ilimitado - 20€/Ano, já com iva incluido.
http://www.proalojamento.com/
Para inícios, a maioria serve desde que tenham um bom uptime.
a rackspot é uma boa aposta.
Se não te importares com velocidade, tens o arvixe que é muito barato e funcional, mas é tipo caracol.
O ideal a meu ver, é teres uma VPS bem configurada onde colocas o que queres, como queres.