Until Wakanda offers a cloud hosting solution, I am using a dedicated box. I looked around and found this to be an excellent starting product:
At the time I wrote this, it was $30/mo as a base package with 10% off if you pay a year in advance. I haven't seen dedicated machines even close to that on a monthly basis.
As a bonus, I can get a couple months free if you use my referral code: b10-2 Thanks.
I sent in my order this morning and had a box up and running literally within minutes. I have a mac that I used for remote control, if you're connecting with Windows you might have an extra step. Overall, as a client of less than 1hr, I am extremely impressed. Just remember when you set up your first solution to change the settings from localhost to your IP Address or domain.
I am actually posting this from my new server ;) Check out the speedtest.net marks!