UK bandwidth has been a practical option for a few years now, decent network trunks are now also available outside London making it feasible to host a datacenter outside the M25 and still provide a decent network connection thus bringing down costs from the high Docklands property costs.
I've just set-up a server with Matt's company, his team seem to be quite capable (we did have a set-up issue, but that was resolved completely with much less fuss than I've had with some other providers). I can't comment on the VPS as I've not used them, but don't see why they wouldn't be of similar quality.
Poundhost are also OK as a budget provider although support is not as good as it used to be a few years ago before they were bought.
cPanel is quite stable now, so you could go with that instead of Plesk, if you are more technically able and not looking to resell services, you can run a server / VPS quite OK using Webmin (which is free)
