Unfortunately, with hosting, a lot of the time the best you can do is "I had a great experience, but ymmv." If I host at xyz and can consistently max out my 5 Mbps cable connection downloading from my server there, maybe you'll have to connect through a crappier route than me, and get higher latency, and worse speed. Furthermore, maybe you and I both get great performance from my site on host xyz, but then you get put on a server with some site that gets DoS'd or slashdotted all the time, so your performance sucks.
Another factor to consider is where the data center (DC) is located. There are various major "hubs" for internet traffic, so if you can get a DC located near one of those, you're better off. For instance, I'm located in Minnesota, USA, and a *lot* of my traffic gets routed through level3 backbones in Chicago, Illinois. I know a bunch of people interested in hosting midwest gaming servers, and they're all looking for DCs in Chicago, because of this fact. I'd like to assume that most hosts will put their own web site on the same network as their client sites, so if you traceroute to their site, you can get a feel for where they're located. Their 10 Gbps link won't matter if they have a backbone 30 hops away from everyone and connect through a NOC with crappy peering agreements.
Getting back to the point, though, my recommendation is to ask for like, a 15-day or 1-month trial from these various hosts. You can set up test sites to really evaluate your performance there (and perhaps ask the community for help testing ... ping times, download speed, traceroutes).
Also, you're quite right about 99.9% uptime not being tremendously impressive (and much less so, 99.5). 0.1% downtime is about an hour a month, 0.5% is almost 4 hours. Even though I just noted this is rather unimpressive (to me, anyhow ... my desktop PC has less downtime than that...), I still find that 4 hours of downtime in a month is probably acceptable, probably won't actually be that high, and will generally occurr late at night. It's reasonable to ask them what their policy on notifying you of shceduled downtime is, though (I've only ever used one host that reliably notified me of scheduled downtime).
In closing, the two sites I've ever used for shared hosting are
DigitallyJustified and
Site5. I also have a dedicated server on
xlhost. I don't really have serious complaints about any of them, and speed was acceptable for general purposes (though, I never taxed the former two significantly, I can attest to having sustained 1 MiB/s transfers from my dedicated xlhost server).