Letharion,
I used to use
Gladserv in the UK. They are in the same datacentre as bytemarks full gentoo mirror.
Then I outgrew a VPS and moved to a whole server from OVH in France. Bytemark used to offer Gentoo VPS but I don't know if they still do.
OVH are dreadful, the support is terrible, in 2013 their Gentoo was still using baselayout1 and lots of other things I had forgotten about.
After looking at it for 30 min, I blew it away and installed my own Gentoo.
OVH are cheap - expect what you pay for.
Hetzner seem to be quite good. I'm in the process of moving to them from OHV.
The link is for recycled servers. They also do VPS.