However, Shimmin warns that Page should be careful to not pinpoint his focus on innovation.

"Believe it or not, I think Google should slow its rate of innovation, focusing not so much on wild ideas such as self-driving cars and instead focus on improving its existing portfolio," he said. "For example, Google Apps should see enough investment to make it a truly unified, mature and -centric platform capable of beating rivals and feature for feature."

Both Enderle and Gillis said Page needs to deal with the company's trust issues.

"Google is at a crossroads," Enderle said, explaining that it appears to be "unfocused, increasingly difficult to work with for partners, and a problem to correct for governments."

"The company's image has degraded to a point where few would trust them, and trust is critical to much of what they intend to accomplish in the future," Enderle said. "It is well past time the founders looked into the mirror and realized they have become a company they wouldn't choose to work with. Fixing that problem should be their highest priority."