I recommend Vidahost, as I manage about 20 or so sites with them. If you ever need support then you are not going to beat these guys, ever. I work with the internet every day, and occasionally come unstuck with sophisticated server settings - but I email them and they go that extra mile to help me out.
They've opened new email ports on their server, owing to port 25 ISP issues with one of my clients - and considered that as part of their service - never asked for a bean. And you know what? When I call them, for a query, and for some reason I can't get through - I leave a message and they ring me straight back!
You may be able to find cheaper hosting than Vidahost, but you won't find better (IMO).