HALF MOON BAY, Calif. – Google chief executive Eric Schmidt passed by the Apple store in downtown Palo Alto Tuesday night and saw a line of people waiting outside. Schmidt joked that perhaps Apple (AAPL) fans just like hanging out at the store, but he assumed they were waiting for the next shipment of the iPhone 3G to arrive.

The success of the new iPhone has the Google (GOOG) top exec excited about his company’s own mobile efforts. “It shows you the power of a device that is a step forward,” said Schmidt in an interview Wednesday at Brainstorm Tech with Fortune senior writer David Kirkpatrick. “The iPhone has a fully functional browser. We can show desktop ads, not mobile ads. That’s a huge change from our perspective.”

Google started to aggressively move into the mobile market in the past year. It is building a mobile platform called Android, and handset makers will deliver the first phones using the new Google software by the end of the year. Google also entered the Federal Communications Commission’s wireless auction last fall and succeeded in getting Verizon (VZ), the 700 MHz broadband auction winner, to commit to building an open-access network.

Schmidt said the innovation and power of the iPhone means better applications and web browsing for consumers and ultimately good news for Google. “The iPhone’s competitors all have devices or devices coming out. It’s really simple. A phone is a GPS, a camera, a computer, and a browser,” he said. The combination of those four means more market opportunities for Google, he added. Schmidt is a director on Apple’s board.

Schmidt predicted that the best applications for social media – now found on networking sites like Facebook and MySpace (NWS) – will happen on mobile phones. One application for Android coming out later this year: A location-based service that tells you where you are, what buildings are around you and what businesses are inside. “The most interesting social applications will be mobile-based because people are always moving,” he said.