I have used pair.com for years and I've been VERY satisfied with them. They aren't the cheapest game in town, but paying a few extra bucks a month is worth the comfort of knowing that my sites are being handled by professionals.
in reply to OT: Web Hosting Service - CGI/DBI/MySQL
My only complaint has been that they have no plan to offer/support Rails, which I've been quite interested in for the past few months.
Dreamhost & Textdrive seem like nice hosts too, which offer PHP, Perl and MySQL (and RoR).