Hosting

VM hosting

• Amazon EC2 (wikipedia). Xen images of linux systems. $74.42/month for 'small instance compute unit'. You are billed $0.10 for each hour your virtual image runs.  There are many prebuilt system images available. The differentiating factors with EC2 are the ability to programmatically start/stop images so you can scale up or down easily, and the 'by the hour' billing. Additionally it is coupled with their Simple Storage Service (S3),which provides storage at $0.10/gb/month plus transfer fees.
• Slicehost. Xen images of linux systems, starting at $20/month. Rave reviews.
• Quantact.com. Xen or OpenVZ images of linux systems, starting at $9.99/month. I've used them in support of my business for over a year, and they have been great. The owner (Tim) is very responsive and candid about what his service can/cannot do, and this is what sold me. I've seen two outages in this time, of less than 3 hours total (to the best of my recollection).
• Lylix.net. Images of linux systems (virtualization tech not mentioned on site). Starting at $10/month.
• VPSlink. Xen or OpenVZ images of linux systems, starting at $7.95/month. The 64mb host at $7.95/month is too small for anything with a SQL back end though, and the next step up is $14.95/mo for 128mb, which is do-able, but just barely. The management features are nice, though.

Web Hosting

• NearlyFreeSpeech.net (wikipedia). Web site in the cloud. Runs on FreeBSD, provides limited services. Charges by the megabyte stored or transferred, so a monthly bill fluctuates by how much the site is hit. Perfect for small budget, low to medium traffic websites. This review gives the skinny.