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.
https://news.ycombinator.com/item?id=3438149
You can pick up a used copy for a penny plus shipping. A couple examples: Pet food delivery (pets.com), same-day grocery delivery (webvan.com), local event listing/registration (eRegister.com). All thing we now have, but which failed despite massive VC funding in the '90s.
It might not be the kind of startup that you were thinking of, since it was hardware-focused, but I was actually there so I think I can tell the story in some detail. What we made was large computers, though we tried not to call them supercomputers. Up to 972 nodes, each a six-core MIPS CPU with direct access (no second support chip) to a very fast RDMA-capable communication fabric. Looking at the boards, you'd see little other than those chips and a lot of memory. I got there in 2006, but the company had already existed a few years before that.
The "bad timing" aspect was two-fold. First, the market just wasn't ready for that kind of low-power/high-density play. It's a lot closer, but still took too long even for Calxeda and SeaMicro which came later. Then there was the funding. Our first generation had done well enough to start a second - likely to be on the order of six times as fast. Since we were building everything from chips on up, we needed a fair bit more than the first gen was bringing in, but we needed it in 2008. Not a good time to be seeking funds. Even pursuing unconventional avenues, we just couldn't scrape together enough funds structured the right way to make a round, and literally ran out of money. All that amazing knowledge now molders in escrow somewhere, except for that which former employees are now applying in subsequent jobs.
If that same talent and effort could be collected in one place now, or even better around two years ago, I still think it could lead to a new computing paradigm. Instead of a few "fat" nodes with more CPU power than the rest of the system can keep up with, we'd have seas of smaller nodes better balanced between compute, memory and communications, and software designed to take advantage of it. In the end, far more useful work done per kilowatt, per BTU, per cubic foot, or per dollar (that was almost exactly one of SiCortex's slogans).
But it was not to be, because the principals saw too far ahead. It's a sad commentary on how deluded (or misled) the rest of the computing industry can be.