Beware and embrace the slashdotting (insert digg, reddit, HN here).
The cache is both your killer feature and your risk. I hope it's statically stored or can be put in memory quickly... are you using Varnish?
Encourage it's use... if people are bookmarking using histori.us and a site goes down, you've just gained a very large audience to your service. But only if your site survives the onslaught itself.
The biggest problem (by far) is disk usage. The rest of the service is very easily sharded, really, as every user is isolated. Solr is also fantastic (much better than Sphinx, in hindsight we should have gone with that for TP), so that can also scale very well (there's even an implementation of it on hadoop).
We'll add the caching feature to the front page as soon as we finish the current round of A/B testing, thanks again (that feature was basically an afterthought, so it was great that you noted its importance)!
http://buro9.historio.us/search/
You can publish sites there (including tags) and refer people to it by giving them a link of the form http://buro9.historio.us/?q=some+query. Personally, I think that's pretty handy for answering the question "do you have any sites about X?"
No items are made public by default, but do note that, when you do make an item public, you are also sharing the cached version.
Thanks again for the feedback, and I'm good for that free subscription if you need it!