When picking an architecture for a service that relies so much on a 'classic' architecture like web maps never underestimate the effectiveness of more traditional hosting solutions like RackSpace Cloud Servers or Linode.
You will have much less choices to make (like use S3 or not, load balancers or not, backups, etc or not and how much is that going to cost?) whose outcome is difficult to predict AND, more importantly you will be able to use tools that you are already familiar with.
Having gone through the same myself some time ago I can tell you that the critical factors in my decision to host a web maps service on Rackspace rather than AWS were:
- Cloud Server are (more) resilient than EC2 instances. EC2 instances are actually expected to fail and they will fail
- EBS volumes fail too (there's plenty of sad stories in the news) and generally have poor I/O
- unless you pick the larger instances I/O contention could be an issue (especially if you plan on seeding the tiles on EC2, rather than copying them over). It could also be an issue with MTBtiles databases
- Whenever you reboot your server the public ip will change: this does not happen on Linode or Rackspace
- You will have to come up with a backup and restore strategy yourself whereas both Linode and Rackspace provide point and click daily and weekly automated snapshots and restores
- If the host running your VPS fails Rackspace will take care of relocating your instance and restarting it on a different server and they will do this in 4h (it's in their SLA). It happened to me while I was on holiday: it felt very professional. Linode should do the same
- Linode has a great availability SLA: 99.9% and they claim great performance because they don't overprovision
- Rackspace has recently come up with a volume strategy like EBS so disk space should not be an issue anymore. Previously if you needed lots of disk space you HAD to get a large instance while on EC2 you can provision storage, cpu and memory with finer control
With this I'm not saying that Amazon AWS is inferior to others, I'm just saying that sometimes traditional hosting solutions can scale as well as Cloud-based ones. A notable example is the StackExchange network itself.
So, in your case I would start up a large instance on Rackspace and then load all the data in a local Postgis instance. Then, after configuring the rendering engine I would seed the cache. A large instance will complete the seeding process fast enough so that it doesn't become too expensive to run. You can store tiles in the fs, MTBtiles, even on S3 (btw, you can serve S3 data on a CDN with CloudFront).
After the seeding completed I would reboot the server and resize it into a small (maybe even 512MB) instance as at that point it would only have to serve static data.
This is getting a kinda long answer so I'm going to stop here. If you want me to elaborate on certain aspects just drop a comment.
Disclaimer: I am not affiliated with Rackspace, Linode, or any other provider I cited.