Well if you look at the list of California cities it's all in the Silicon Valley area, so if anything it makes a little more sense considering their HQ is there.
The area around Stanford University (Palo Alto, CA) already has Google Fiber run to most houses. This was their test-bed before deploying to other cities.
The other thing that people forget is pretty simple: Most cities have "Cable Charters" with one provider (Comcrap, Time Warner, Cox, Charter, ect ect...) that don't allow competition with other providers. Most of the cities own their own fiber, they just need a company like Google to come in and better manage it...