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: <a href="http://www.linode.com/avail/" rel="nofollow">http://www.linode.com/avail/</a>
<a href="http://prgmr.com" rel="nofollow">http://prgmr.com</a> 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.
These guys have a good reputation:<p><a href="http://www.gandi.net/hosting/" rel="nofollow">http://www.gandi.net/hosting/</a><p>They're not in the UK, but in France... Git is "being implemented, and will be released in the next version of the website."
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.<p><a href="http://reviewsignal.com" rel="nofollow">http://reviewsignal.com</a>
Rackspace cloud has servers in the UK.<p><a href="http://www.rackspace.co.uk/cloud-hosting/" rel="nofollow">http://www.rackspace.co.uk/cloud-hosting/</a>