You might want to check out Gandi's, too. I have no experience with their VPS service, but I've been using them as a domain registrar for ages, and I've been very pleased with them as a company.
_________________________
Bitt Faulk