Cheap hosting with no random downtimes??

I'm concerned about finding a cheap hosting provider that can manage their servers well. Currently, hostgator has started to have unexplained downtimes on my monitoring service at night and a couple of times during the day. Nothing posted in their planned maintenance threads. I'm assuming that their natural cycle is to put new customers on a server until it generates complaints and manage from there...if it doesn't stablize I need to find a new host.

So is anyone using a cheap hosting provider that is consistent and snappy if properly configured w caching? Or anyone been through this with hostgator, do they eventually stabilize? Otherwise I am going to have to do an RFQ for hosting services. sigh.