Midphase rocks for me. They're always on top of things. And you can talk to a real live customer service person, that really seems to give a shit.
Any shared host is going to suck with decent traffic. But no one should have that kind of downtime. That's nuts. I have a dreamhost account, but I don't have anything hosted on it except parked domains. It's pretty cheap for that.