It depends on your Budget. I would not get any Dedicated VPS coz thats just crap and is not Dedicated in terms of resources. If you have the money then go with Rackspace. I really like their support.

If you just want to start out then try Cloud Hosting though Mosso, its a Rackspace Company. The basic start with 100 bucks. Since its in the cloud. you can deploy webs apps in different architecture.