Well as you are saying a DEDI for a Proxy...that means that you are getting some serious traffic and as per your previous post in anohter topic about cpu limit..that would only mean that you are getting huge traffic aand need a better solution so this is what i would prefer.

This is considering the fact that your current host is on a high end server.

So you would need something like:

P4 3.0ghz w HT
1.5-2gb ram
40gb-80gb hd (any smallest)
10mbit unmetered
Cpanel
Pro-Active Management

You should look into high end servers if your proxy is really resource intensive.