That really did suck. I kept hitting F5 to see if the site would load like every 20 minutes during the work day. Unfortunately, I don't have any advice regarding hosts. The reality is, I think they all suck. Unless you're a top-tier customer paying loads of cash monthly to have dedicated servers and T1 connections, you're probably up excrement's creek when something goes wrong.
What about Amazon? I know a lot of big businesses use it, including Netflix. I've never really looked into it, but if their backbone supports Netflix, one would assume uptime is pretty good.
Amazon Web Services