If all you want is VPS that is cheaper than AWS then Slicehost may be the thing for you - http://www.slicehost.com

EDIT: I forgot about Linode since I haven't used them myself. Here's a comparison between the two from last November: http://journal.dedasys.com/2008/11/24/slicehost-vs-linode