I use SurpassHosting, I have few dedicated servers from them. Currently I'm very happy with the service and support they are providing and I certainly do not see myself changing hosts for a very long time to come.
I use neoboffinhosting.com. It's not a big company but I'm very happy with the support. They are really helpful and get back to you promptly. I don't like to wait for days for the support from other companies.
Any good webhost these days have very few downtimes. If your host has more than 1 outage every month it probably isnt that good heh.
No host is 100% stable. All hosts have their ups and downs. If your host has a minimum of 99% uptime, they are a stable company. If your host offers over 99.50% uptime, their lying.
I'm hosted with unknown companies that have extremely cheap services, but i use them at my own risk, my dedicated servers are unmanaged, and the reseller accounts are often down.
If you need quality hosting and good uptime, try Hostgator or Globat