I think Whatsapp is another great example - afaict the key innovations there were using cell phone numbers as user IDs and running on every platform known to man. Just works. Dropbox and Imgur are two others.
The saying should be 'first decent mover'. There's a world of difference. Often it's the one that comes along and takes the basic concept and executes it in a way that makes sense to a larger user base is the one that wins. Too often the first versions of a product are still cloaked in the terms and features of the technology that underpins it.
They had the highest number of VPN nodes all over the world, a dozen of IPs per country compared to 1-2 for other services.
The app was also easy to use and worked without problems, had no disconnects AND disabled your internet connection IF you did get disconnected for whatever reason, not exposing your real IP.
That may have been lip service though, because even their ToS stated "we'll turn your info over to the authorities at the first request, no offense" :-) but technically, it worked well..
Dropbox was gamified, a bit, in my view, in that I had loads of people who'd invite me to dropbox, because they'd get extra storage for getting me to sign up. Maybe it's not real gasification because they didn't get badges?
See also MP3 Players and smartphones. Both markets looked boring and well-trodden until Apple blew fresh air into them.
The key to this kind of success is finding a segment that is currently niche but won't be for ever. Cloud storage, mobile internet messaging, portable MP3s, portable Internet -- all potential mass markets that were kept niche because the products in the market didn't have mass appeal.
I had tried many solutions before this, and they were all, without exception, a pain to use and usually ridden with ads and weird interfaces. You usually felt dirty going to download a file from the website.
I wanted to replace it with free software, but it's still a PITA --syncthing seems the best so far, although it requires more experience to be a DB killer
1/ completely platform-agnostic
2/ completely automatic
None of the previous attempts at this were even remotely addressing those two (simple) concepts... and they still aren't!!
Fast, uncluttered, no pay-for-rank
It's easy to forget there were lots of search engines before google. It was a boring "done" field
How old are you? The algorithm made a difference :)
Why would people use google? It was cool and new, had a great story... and made all tradeoffs in favour of letting you get on with searching, without a whole lot of portal BS/spam, fitting OP's criterion.
Google's biggest advantage today is speed - esp google suggest is unbelievably fast. It required a huge investment and knowhow that its less profitable competitors just can't match.
But the "some" was one of my PhD supervisors, who didn't mind a bit of thought-provoking... unlike today's HN, sad to see.
Even if the algorithm wasn't all that good to start with, it was damn fast, and clean, and no ads, so... you didn't mind refining a search a few times, because there were no annoying ads to slow things down.