Try
HostingMatters. They run their servers on Redhat 6.2 boxes. Great customer support, I have sent them emails in the wee hours and on the weekend. Generally always get a response within an hour. They also have an
online forum which tells you what they think of customer service. A lot of hosts out there would dare have an online forum for all the complaints they receive. Read some of the comments or post over in the forum before you sign up and see what kind of response that you get. They are also very affordable. No setup fees and MYSQL databases starting at $11/month.