Heroku is really good. You will probably have more downtime than them unless you hire a whole team of operations and admins and pay a lot of money for hosting. It may also take a while to build out the deployment and development tools they have.
We moved all but one of our Rails apps off of Heroku precisely because of the frequent downtime -- or, rather, that was the last straw; there were other issues, notably the difficulty in debugging production issues, that had us already debating such. Heroku has gotten somewhat better, but it's still down far more than anything else that we use. (And we have services spread across Linode, Rackspace, AWS and the mentioned one app on Heroku.)
You'll have better uptime in most cases with a standard nginx / passenger setup on a $20 VPS than you will with Heroku.
The competition for something like Heroku is EC2, VPS, or dedicated servers, in commercial colocation facilities. A good hosting facility is going to be a lot closer to 99.995% uptime for network and power to the box, but you can of course screw up past that point on your own.
99.9% is very doable. If your sites have less then you should consider hiring better staff.
Also the heroku figure (99.97%) is a lie - just skim their status-page.
I'd seriously consider Heroku if they were in multiple regions (fuck AZs, those are a lie). There are huge advantages to a PaaS in terms of speed and lack of hassle, and a well run PaaS is better than most developers at operations, patching, security, etc. (We're kind of unique in that we're better at operations than development, though.)