Linode and arpnetworks are what I use at the moment. Arpnetworks is more on the cheap side but I use them only for freebsd and for linux I use linode (I was a customer of prgmr for a year before and only had 1 minor downtime with them for a hardware failure.)