dedicated boxes and VPS are extremely inexpensive. I use 1and1 for all my needs, I have hosting, a vps and a dedicated from them.
Their vps(Virtue private servers) all come with amd dual core opteron 1.75ghz, ram varies from 128MB dedicated with 256 bursts to 512MB dedicated 1024MB bursts, space and monthly transfer are extremely good for the price and 1and1 all hosting/servers are on a true 100MBiT pipe. which you don tpay extra for, you dont pay extra for 64bit support or plesk either. You also recieve a free domain for the vps. Currently they have a special (ending in 7 days) if you sign up for a vps 3 you pay 1$ setup and 3 months free.
The dedicated servers are great, from 99 to 399 a month from single core to quad core, no less then 1gig(99$one) and up to 8gigs(399$one) of ram.
link
total experience with this host: since 2005 with Bussiness hosting, Developer hosting, VPS3, and a root server 1.
great thing about 1and1 they have lax terms you can do anything you wish on your box as long as it isnt something like terrorism.
and Im sorry with my knowledge of running servers, you cannot run a lag free server with a 2MBiT uplink you need atleast a 10MBiT, but it is preferred you have a 100MBiT