I looked around a lot, and my conclusion was that the best linux VPS hosters were linode, slicehost, and gandi (now that they are out of beta). I have currently an account on each to test them. Each has its pros and cons, choose accordingly to your needs, there is no clear winner. (latency from your home, limit on bandwith or amount transferred, limit on disk I/O, timezone...).
My main account is on linode since Jan 2009 (was on slicehost in 2008), but I have friends on linode and gandi (and my registrar is gandi because they have the best ethics in the business). You can't go wrong with any of them, and if you go wrong anyways, it is a breeze to migrate elsewhere with VPS (tip: pay per month at first, and google for promotion codes).