UK Shells do a perfectly decent job of this - they run Linux accounts with shell access, MySQL and PHP for less than a hundred quid a year. Their help-via-email (or web) is always knowledgeable and generally quick. I've been with them for about 5 years and have run a small drupal site there for 18 months or so.

At the end of the day with hosting you get what you pay for. Cheap hosting means lots of sites crammed onto an underpowered server and being at the mercy of someone else's badly managed processes eating up up CPU or another site on there getting lots of hits. You might like to have a look at virtual machines with Bytemark too but whoever you pick, see whether you have an easy upgrade path in case things go well! With virtual machines, this should involve no downtime.

I've tried most of the host but 1&1 have been always my favorite. Better got for quality rather than price.