If you are okay with working on bare metal (i.e. no virtualization out of the box) than Hetzner (www.hetzner.de) is a very interesting partner. My experience with them is very good. Ex-colleagues are also happy with them.