+1 para WebFaction.
Eu quando comecei com Django utilizei a KingHost, na época eu tinha alguns sites em PHP com eles. Me frustrei com a instalação na infraestrutura deles.
Recentemente fiz um site para um parceiro que possui os emails no UOL Host e utiliza alguns recursos de Email Marketing e não queria mudar de hospedagem.
Hospedei o site no WebFaction, meu host atual para web sites feitos em Django, e apontei no DNS no UOL Host para o servidor do Webfaction apenas os endereços de Web.
Ta perfeito.
Para aplicações mais avanças eu utilizo o Linode configurado com Nginx e uWSGI e estou estudando Heroku também.
E como o Renne comentou, existem principalmente no exterior muitos serviços de ótima qualidade, é só dar uma procurada e o preço e indiscutivelmente melhor.
O Webfaction por exemplo a hospedagem basica é $ 9.95, e o suporte é muito bom e eficiente.
Outros pontos positivos é a documentação, que ensina boas práticas para otimizar suas aplicações em django inclusive. E a facilidade de fazer deploy é muito boa.