You really don't need a VPS yet at this stage, but I can recommend a webhost for shared and/or cheap-end dedicated servers.
www.crissic.com has decently priced shared, and their support is awsome. Been using them for a long while now and cannot complain.
They also have decent dedicates, so if you go with them for shared, they can easily move you off to your own dedicated once it is actually needed.
They also have some dedicated sales:
http://crissic.com/dedisales.html
Pentium 4
512MB DDR RAM
60GB HDD
2000GB Transfer
5 Dedicated IPs
$49.99 per month -- just within your budget.
They have more expensive servers, as well as a cheaper server for $39.99. They are based over in Pennsylvania, USA