http://rimuhosting.com now have a datacentre presence in the UK (London). I find them very useful but best of all they have very, very good support. They are NZ based.
I second rimuhosting, using them with both my companies (Soocial.com and eightmedia.com)
ovh, vectoral (netdirekt dc, not reselling), leaseweb I've had personal experiences with. their support generally sort of sucks (at least they reply to you..hehe).
oh, ovh doesn't sell to people living in certain countries. they said they'd change their policy sometime soon, but have yet to see it..
I am very happy with http://hosteurope.de .. excellent service, good hardware, barely downtime. They have VPS instances and also dedicated servers for prices you can only dream of in the US.
You can find cheap dedicated servers in france at www.ovh.com . They have a lot of OS distributions and if you can manage your own servers it's a good choice. I work in an spanish ISP and we exchange traffic with them at AMS-IX so it should be properly connected to all the important european ISPs.
OVH also have sites for UK, Spanish, Portuguese, Italian, German and Polish customers (see the flags at the bottom of OVH.com), not just France. The pricing does seem to vary depending on the country though (the cheapest UK 'real private server' costs 9.99GBP in the UK, and 9.99 Euros (7.91GBP) in France).