Hosts that I've been very happy with: Rackspace Cloud, WebFaction, and Linode. If you don't expect too much load or traffic at this point, the easiest/cheapest solution would be to go for WebFaction (or Rackspace Cloud if you need a VPS. They have a slightly cheaper entry point pricewise than Linode).
