If you want a VPS for Lisp (SBCL), I recommend Slicehost.

I tried Linode out for a week, but had trouble getting SBCL (w/threads) running on their new Xen nodes - but their support was spectacular.

I've also been a long time customer of OCS Solutions. Not the best pricing but they're just too friendly and responsive for me to move.