Tonight I gave a presentation to the Waterloo Region User Group about choosing a host for a Drupal based site. We talked about the essential requirements on top of the Drupal requirements, types of hosting, and our experiences with various hosts. I think the results of the discussion can be summed up as "you get what you pay for"! I've attached the presentation slides for anyone interested.
The essential features I noted as being important include: