[KingJ]

While co-location is best in the long-run, it has a high up-front cost and requires you to be able to travel to the datacenter or safely post the server there.

I would suggest having a look around http://www.webhostingtalk.com/, despite it's name there is a lot of information on there about server rental and colocation. Have a look at some of the reviews and compare the various companies that meet your requirements.