I've had sites on linode and slicehost, and have found Slicehost to have less downtime, packet loss, network problems (unreachable), and so on. I'm satisfied with both, overall.
There are three incidents listed in the past two weeks of packet loss, routing issues, and so on for 1-3 hours. There were other issues in May, I don't know where those are listed now.
Yes, it's only going down for a couple of hours at a time. Considering I'm using the server for images for a medium traffic website - an hour or two is VERY noticeable to my customers, and as noted, it adds up to more than the downtime on my Slicehost account (St. Louis).