I've been a delighted Rackspace user for over a decade (!!) now. Recently switching from dedicated server to their cloud service.

They also have a startup program where they'll subsidize $1000 of hosting for six months: http://rackspacestartups.com/