IME there is no such thing as "no downtime" but you can get pretty darn close and if you're lucky get a web host that makes it up to you if/when it does happen.
Anyway, after doing some research we finally went with
Crissic.com. They're still pretty new but I'm super pleased with them so far.
They have fantastic customer service and excellent prices. For the same price I was paying at HostICan for a VPS I now have a dedicated server with even more memory, storage, etc. The owner knows his stuff and has fantastic staff as well... they even gladly moved my site from the old host to them and did so without a hitch. As someone who's new to this admin stuff the Crissic folks have also been extremely patient and helpful.