Not endorsing these guys since I have no idea what their availability is in practice, but isn't 3 nines a fairly common SLA? I believe this is what I get at Linode and Digital Ocean.

My experience with them is that their reliability is actually below that. We moved to Softlayer, couldn't be happier.