I don't have any recommendations for a host, but I want to ask if you got some money back from your provider? They typically will have an SLA with you, so you may be able to get a refund for downtime, especially unscheduled downtime.
We've done this with our provider a couple of times, and received money back for what basically amounted to bad service, and we haven't had any problems since. :)
What sort of down time are we talking about here. You mention short down times, but is this more than a minute at a time and frequent?
With shared hosting you couldn;t realistically expect much better than 98% uptime. There are some very reliable hosts out there, and some of those will offer you a virtual dedicated server and/or a fully managed server, but in reality 100% uptime is very nearly only a dream. Fpr instance, updates to a web server's OS will create very short downtime intervals (usually undetected).
You might get 99.9% uptime with a dedicated server, but there can be no guarantee since at the very least there is so much that can go wrong between a user and a web server.
I've been with a particular host for 5 years. In those years, they've been down ONE TIME - for less than 24 hours. This was occasioned by a fire in their building - on another floor - which took out the building's electricals.
Great folks. I would NEVER complain about "uptime" with these people.
Network uptime is frequently maintained well by dedicated hosting centers - but it means nothing if a hard drive fails or memory gets corrupted. The only real way to guarantee good uptime is redundant hardware.