It has also become a key mobile player with its Android platform and with mobile versions of its various services and applications. The company has entered the enterprise software market with Google Apps, and its Chrome browser and operating system could leave it poised to become a provider of a new personal computing platform.

But Schmidt was also at the helm for some controversies Google found itself in over the past decade, including a number of privacy-related fiascos and thorny copyright-ingringement lawsuits from book publishers, media conglomerates and major companies.

A big challenge for Page will be tackling the influence of social media and social-networking sites, namely Facebook and Twitter, which have encroached on Google's territory both in advertising and distributing online content.

"One of the things missing from Google's strategy has been the social component," Gartner's Weiner said. "I think the ability to move on a major social-networking strategy may come more easily from a younger CEO." In fact, Google's struggles with the social Web may have played a part in the CEO switch, he said.

Google also faces tests internationally, especially in high-growth areas like China, India and Russia, where the company's track record has been mixed, Valdes said.