Arguably Loopt (Sam Altman's startup), which was doing a locality-based social network in 2005, before the iPhone. Subsequent attempts (Google Latitude, etc.) have also failed, but I suspect that's because the market still isn't ready.
General Magic. This Apple spin-off was doing a handheld computer in 1990, way before the technology or population was ready for it. Interestingly, basically all of the modern smartphone industry comes from General Magic alumni - Tony Fadell (father of the iPhone) and Andy Rubin (father of Android) both worked there.
First generation of search engines. It's not just a matter of being smarter, PageRank wouldn't have worked early on in the web because the link graph wasn't dense enough to get useful signal out of it.
LiveJournal, Xanga, EZBoard, and the first generation of social networks. They had some traction with early adopters, but the problem was that their userbase was weird enough that it drove off mainstream adopters, rather than bringing them in like Facebook did 5 years later.