This will depend on the type of application you're running. The first thing to determine is how much infrastructure you need. How many concurrent visitors are you expecting? What sort of traffic spikes do you want to be able to handle? Is this a static HTML web site or a dynamic application requiring a back-end application server (PHP, ASP, ColdFusion, etc.) and a database? You should load-test your application in a development environment to determine how much load you can handle and whether or not it is above or below your anticipated traffic levels.
Once you know how much equipment you will need to handle your anticipated load, then look at various managed server providers such as SoftLayer. There are dozens of managed service providers who can give you various levels of service depending on what kind of hardware you need, how much of it, bandwidth requirements, etc. Certainly ask them about their connectivity, facilities, battery backup, generators, failure response times, etc. Many providers will not offer an SLA unless you ask for it and pay extra for it.
As for uptime, you get what you pay for. If you're at Joe's Managed Server Co. with a staff of three, don't expect much. Go with a reputable managed server provider that owns and builds out their own network with 24/7 support staff on-site.
Also, consider your future growth. Will the provider be able to upgrade your equipment quickly if needed? Can they provision additional bandwidth or servers within a few hours?
I would recommend contacting several managed service providers and reviewing your needs with them and comparing costs. They do this for a living and should be able to help you determine exactly what you need to meet your needs.