I have 2 servers (Dual Opteron/2 GB RAM) from LayeredTech and SoftLayer which I highly recommend if you want to go dedicated. Their servers should be able to handle your proxy sites. Good luck.
Softlayer is a solid provider, they may be more pricey compared to a layeredtech but they offer a lot more feature wise. Softlayers panel to do reboots and all sorts of things destroys layeredtechs non existent portal.
Depends on where you want to set up? Europe, US or Asia? I'd go for unmetered so you don't need to buy expensive overage halfway through the month. Óther resources comes down to what proxy script you are using and your config --- but as stated above, RAM always makes a server admin smile.