I think one of the big innovations Google Search brought to the table is the Google doodle. The main features of their interface have remained the same for over a decade: type what you want to search into the box, click "Google Search" and a list of results appears with links and brief intro text. There's new stuff on the search results page that wasn't there ten years ago, but it doesn't really interfere with the functionality. Such a simple interface would feel stale after 10 years for most applications, but having the Doodle means it changes over time, keeping it fresh in a way that doesn't interfere with the functionality. This allows them to keep users from getting bored with their product, while also not forcing users to learn a new interface with every refresh.
I have a lot of problems with Google and don't use their search (I use DuckDuckGo). But I think we can still learn some valuable things from them.