1. Dedicated physical server (starts at $100 / month).
2. Web service such as Amazon EC2 (starts at $72 / month).
3. Virtual Private Server (starts between $20 to $50 / month).
4. Web hosting such as HostMonster, SliceHost (can be as low as $5 / month).
Our considerations were: a dedicated IP that would not be blocked in China, the ability to run long-running scripts, no CPU throttling, and enough memory and bandwidth to handle traffic spikes. The top three satisfied these constraints, and #4 did not.
We ended up going initially with option 3. A good place to read reviews for web hosting providers is the WebHostingTalk forums.
We wanted a VPS with good uptime, and technical support who were responsive and competent. After reading a number of reviews, we ended up with FsckVPS, which has satisfied our requirements so far.
Questions? Or want to share your own server hosting stories? Leave a comment.