I think your probably looking at a P4 2.8 with atleast 512 megs of ram. The hard drive should be 8 mb cache size, atleast 40 gb. The connection is what you shoud probably focus on. Many will try and put you on a pipe where there capacity is extremely low or of poor quality.
your price point should probably be around $120.00 - $140.00 for a quality host.
I know of many who can offer such services.