Sidenote: Linode will do 32bit images, which so far, has been proven to lower the memory needs of some processes. SliceHost/Rackspace Cloud only run 64bit images, AFAIK, unless this has been resolved since I last checked. You also get 512mb at Linode vs 256mb at SliceHost for the same cost.

Learning curve is steep, I'll agree, but totally worth the investment in learning. When it gets to be a pain, hopefully your business model allows for you to hire someone to handle day to day operations. :)

Thanks! I wasn't aware that somebody had created a search utility for hackernews. :)

+1 Web Faction - starts you off with shared hosting with some dedicated memory for your application. You can add more as needed, for a small fee.

+1 Linode - Best bang for your buck for a VPS loaded with features and reliability.