They innovated on three frontiers - search engine algorithm, intent based advertising, and data center/infrastructure technology. A startup has to be really good at one thing to succeed. Google was really good at 3 three things right from it's early days.
As much as I like google, I doubt they're as good as that. Their search and advertising is essentially a monopoly because they have such a data lead over anyone else. That's why facebook freaks them out because they know how having more data is the secret sauce. Their data center innovations don't seem all that incredibly innovative. If they had robots whirring around I'd be much more impressed.
I mean in their data center. Also, I'd be more impressed if they actually got the self-driving cars out to the world. It's been 5 years now. Google has a problem executing, they're lulled by their one success.
If you live in the Bay Area you see the automated cars driving Google Employees to work all the time. I used to get an SMS any time somebody saw one (they are very distinctive) - but not as often, because people are starting to get more used to them. Though, they are still pretty cool to run across.
I'm impressed because people have been trying to nail this problem for decades. Try convincing people that a few million automated half-ton canisters of metal going 60 miles an hour are safe. An early success will win investors or make a nice press release, but developing a rigorous, safe product of that complexity and risk is a long slog. It's got to be so well understood it's boring - then it's ready for massive public use.