LunarPages has great support ... they may be kinda pricey. 2x80GB HDD, dual 2.8MHz CPU and 4GB RAM is our package at work, I think ... about $110/month.
I'd prefer to work with FreeBSD instead of CentOS ... I kinda wish we could move to rootbsd.net --- looks like you could get 500GB HD, 2GB RAM on a Core2 Q8200 for 99/month.
And, of course, I wouldn't be true to myself if I didn't suggest just grabbing a box (old, or new), sticking FreeBSD on it, and getting it into someone's datacenter or machine room via begging or bartering ... :-P