I am starting proxy tops sites, I don know whether do we required dedicated proxy hosting or just normal one. I will just host proxy site name using proxy top site script. I wońt start proxy service there.
Being a web host i know personally that proxy sites need heavy resources and this is the main reason dedicated services would be recommended.
I have hosted a proxy topsite on my reseller account. It hardly needs any resources. You can go for shared hosting.
Guess its been answered by all the people here! If you are looking for good shared hosting plans take a look at my signature or drop me a PM
Go for premium hosts very reliable and highest quality support you could ask just have a look at http://www.vip-hosts.com/ to find any premium host