I've been using Linode for almost two years now and can't fault them; they're the best hosting company I've dealt with. You create and bootup “Linodes”, which are VPS's (Xen based) running your choice of Linux.

Other recommendations if you have a bit more slack in your budget: Amazon's AWS or Hetzner (not UK based, but it's hard to notice – ping their servers).