As premature as it is right now, I'd still like to ask for your recommendation for a good scalable LAMP deployment. I will probably launch the beta with a single box, or a web server and a database on two boxes, but i'd like to know that the hosting service I choose can grow with me and my needs, without having me shut down in the middle of a growth boom and move elsewhere.
I'd appreciate advice from someone who's a few steps ahead of me and has launched a LAMP based web 2.0 application.
Start with Rackspace's Cloud. Full LAMP stack out of the box and it scales like crazy, and it's pretty cheap.
Also if you ever wanted to move to a hosted situation, they will move your installation for you -- their customer service is legendary.
If you would prefer a non-cloud-based solution, such as Amazon's EC2 or Rackspace's Cloud, I would recommend Slicehost. For $20/mo you get a Virtual Private Server (VPS) known as the 256 slice, which includes 256MB RAM, 10GB Storage, and 100GB bandwidth per month. Some of the things that I like about Slicehost, is that I know exactly what my costs are each month (they don't vary with usage as the cloud-based solutions do), and I get my choice of Lunix distribution (personally I prefer Ubuntu). All slices include a dedicated IP and RAID-10 disk storage.
I've used Slicehost for almost 3 years now to host both customer facing websites and to create internal company intranets using OpenVPN to limit access to employees. Their customer support is great.
Slicehost originally started in St. Louis as a small VPS, but they have since been bought by Rackspace. I view this as a plus, since if I ever need a cloud solution I can stay within the Rackspace family.
If possible, I would prefer not to deal with the operating system -- installation, performance tuning, and security patching. Therefore I'd personally prefer a provider who delivers a execution environment of my choice (.NET, PHP, Java) over one who delivers a bare-bones virtual PC. In other words, while Amazon EC2 is great, it is IMHO a better fit for larger, later-stage companies.
So my suggestions would Rackspace Cloud (already mentioned by Jason) be and Joyent. Joyent has been around for years, did cloud computing before it became fashionable, and has some very happy customers too -- worth looking at.
Windows Azure will actually work with PHP as well, and offers some very nice and highly scalable storage API's. I personally would never consider Microsoft's platform for PHP hosting, but maybe that's just a unfounded prejudice nowadays.