It is indeed like deciding who your ISP should be - everyone's needs are different and to some extent it's a matter of "horses for courses".
I do not claim to have any great knowledge of VPN providers but, for what it's worth, after experimenting with a one month "one-off" payment to a number of the cheapies to try them out, I settled on VPN-UK -
http://vpnuk.net - and don't have anything to grumble about. The connection seems to be reliable and, while I understand there's bound to be a slight speed loss due to the nature of the beast, in real life I haven't actually noticed any difference, they're certainly not badly congested.
My own priorities?
(1) A UK server - some don't have one, and it isn't just the BBC where an overseas IP address can cause problems.
(2) The ability to send e-mail, not just receive it, via the VPN - some don't allow this, to deter spammers from signing up, but I don't want to mess around temporarily disconnecting from the VPN just to send an e-mail, thank you!
(3) Use of the OpenVPN protocol, not just PPTP.
Personally I have no interest at all in torrents etc., any of the "media" stuff, but they do say in the FAQ that apart from on their USA servers they don't block P2P, so might be worth you looking at.