Det kommer helt an på dine behov. Så længe hosten understøtter php5 kan WordPress køre på hvad som helst.
Selv har jeg har dog rigtig gode erfaringer med at hoste WordPress på en VPS med rigeligt RAM, så alt kan caches i memory. Jeg har set WordPress hosting fra 9,- til 10.000 pr måned, men det kommer jo helt an på dine behov.
Jeg er personligt fuldt ud tilfreds med at benytte Blanye webhosting. De har både lavpris-webhoteller og mulighed for nogle interessante cloud-setups til mere tunge løsninger :-)