I'd say linode, I've had great experience with them, you get your own machine, so you can stack it however you want, pricing is reasonable, service and documentation is great. Heres a link to uk based servers: http://www.linode.com/avail/
Thanks for the tip. I already have a Linode vps actually and it is great. I should have been clearer however, I'm really looking for a managed service.
My client will pay, so I'm looking for something that will still be around when I've moved on to others things. And the hosting firm will take care of patching, backups etc..
http://prgmr.com is my favorite. It's just straight-up simple hosting by a team of people who know what they're doing. Ubuntu is so simple that it doesn't make sense to have your hosting provider also install software for you.
This. (Disclaimer: I'm not connected to prgmr.com, other than being a satisfied customer for years.)
You can get VPS's small as you need, with pricing to match. Great for bootstrapping on a shoestring.
You can use whatever distro you want -- Ubuntu, Debian, CentOS. You can use whatever version of that distro you want -- you can do an OS upgrade or downgrade whenever you want.
The tech support is friendly and competent. The owner's willing to personally talk to customers.
If you're knowledgeable, the tools to do almost anything you need are included. If you know how to fix something, the out-of-band console will let you handle almost any issue remotely. For example you can reboot in single-user mode or even initramfs. In contrast, many other hosts use half-baked web UI's and/or require filing a support ticket, with hours or days of turnaround, for even simple issues.
It's really flexible. You can use Ubuntu or Debian if you want to get up and running quickly. You can use LVM to make backups easy. You can install BSD. You can even install a custom kernel -- just about anything with Xen guest patches will work.
The only downside (based on your stated preferences) is that it's US-based.
My startup tracks web hosting providers and what people have said about them publicly. It's mostly US focused though. I would look at the VPS section, companies like Linode (already recommended) are rated quite highly. No host is perfect, someone is going to have a bad experience with every single company. Our goal is to try and get enough data to be able to compare the average opinion of a provider.
