Model yourself after TurboTax -- multi-level wizards that ask if you have any of these needs and if so, it drills down to more specifics.

There are going to be single-host people and multi-host people. Their needs are very different. A bastion host might seem like overkill for a single host. If you can directly ssh into your db machine in a multi-host environment then I think you might be playing a little fast and loose. Allowing traffic to leave most hosts to the outside world is also something you should authorize on an as-needed basis, though with todays heavily-integrated applications this one is much harder (and often forgotten.)

Of course, since you are creating these AMIs and know the version of all the software on them, emailing me when I need to rebuild my machines on your latest images is a big value-add. Keeping up with security patches is a PITA. Let me also add in some common frameworks to include in your emails as a v2 feature (rails, php, java..)

Subscriptions.

Also, do remember that you're eligible for the PICPC-VC follow-on round! Ping me if you're interested. It's $50! Plus, I know your space pretty well.

An automated made-to-order system would be useful. Allow customers to select which programs/libs they'd like to include from a list of checkboxes. That way they can order a secure image with their custom stack pre-installed. I would pay you for that luxury. It might be too difficult with all the possible ways things need to be configured by the user (setting up MySQL, for example).

A way to easily audit the image to ensure there's no 'special sauce' you left in. I realize it's no small feat, but I'd be a lot more likely to trust and use such an image if I had a way to make sure it's clean. (One way is to automate the process by way of script(s) that you leave up to the user to understand and review, whether they're Chef or Puppet or whatever else.)

Related to someone else's question, it would be great to also be able to use these images locally for development (e.g., via Vagrant, even if another step would be needed to import the images etc)

I'm not super up to spec with how Amazon works - could I also download these images and load them up in Vagrant/VirtualBox and or find a way to put them on my Linode machines?

Thanks a lot, this is going to save us a lot of time and worry.

No particular recommendation, just one vote for Rackspace images here.

Doing "private label" editions for people who are willing to pay you a premium.

Realize who your core target audience is, what they try to do and make it work effortlessly for them.