Is it appropriate to ask for recommendations for Drupal hosting? I'm unhappy with some of the changes my current provider has made to my account and I am starting to look for a new place for my sites.
In general, no. See
For the reasons why. If you are teaching someone how to evaluate a Drupal provider then perhaps.
It seems appropriate, to me. There are hosting providers that support Drupal, and some of them are listed on Drupal.
It is a Drupal related question as you are looking for a hosting provider which is able to give support for the problems you find when running Drupal on their server. A generic hosting provider that doesn't know much about Drupal requires you to investigate the problem, and them report it in term they can understand; vice versa, a Drupal hosting provider should be able to understand a problem even when you describe it in "Drupal" terms.
The question should probably be a Community Wiki, as any answer would be equally correct.
I would also suggest to specify which requisites you need, to avoid generic answers like "I use this provider, and I am happy."
I agree with @kiamlaluno. A Drupal hosting provider needs to be prepared to provide at least three(3) levels of support: Product layer, Infrastructure Layer and Database Layer.
As a MySQL DBA, I have serviced many Drupal Clients with different DB Configurations, different Replication, and different High Availability Topologies.
Most companies using Drupal focus mainly on the Product Layer and how PHP is used to harness Drupal. Without giving proper attention to the other two layers, Drupal seems to be cumbersome. This equally true for all other CMS products.
In summary, look for a Hosting Provider to offer all three levels of Drupal support.