I personally would recommend a 512mb Linode. I'm not sure what you consider expensive. With my budget (which may be drastically different from yours, or might be close to the same) I opted for the 512mb. It's like $19/mo but it's an amazing service. Full control over the VPS, root access, pre-made stack scripts which you can use to deploy a linux distro with one click and have it install all your server software and configure it from the start.

Their documentation is amazing, they have tons of tutorials/how-tos on everything from basic linux admin stuff to advanced topics.

Check out this performance comparison. Some of the info is a little old but I think it's still useful. I wouldn't take it all to heart but use it as another resource in your search.

http://journal.uggedal.com/vps-performance-comparison/

edit: there have been a number of ask hn: vps thread's and it seems like Linode gets a large majority of the votes from the users here (from what I've seen, I haven't looked through all of the threads).