San Francisco, NYC and Boston because they are big tech hubs where a lot of Googlers live and Washington D.C. because it is the seat of politics in this country and the best way to show what good can happen when we have broadband connectivity.
In fact, rolling out Google Fiber in the capital cities of each state makes the most sense in general. You lobby the political class by giving their home base (state capitals) excellent broadband.
First, AT&T is already in the process of rolling out fiber to the home, or in some cases, fiber to the node with last mile copper. They have faced nothing but problems trying to do this from people in the city: http://www.sfgate.com/bayarea/article/Groups-sue-S-F-trying-...
Density can be a nice benefit, but lack of space makes it hard to place the equipment necessary to serve fiber.
Second, a local provider Sonic.net is also rolling out fiber by taking the approach of starting in the closest thing San Francisco has to a less dense suburb (the Sunset). They've faced exactly the same issue (battles over placing Utility boxes).
But the Mayor thinks that WiFi is good enough. :-(
ATT's last-mile copper solution will barely be better than their current "Uverse".
The City (SF) has tons of fiber running all over the City. With some infrastructure investment, it would not be hard to use that as a backbone for municipal fiber. Residents can then sign up with any of the 3rd parties to jump on to the Internet.
SF High Speed options:
Comcast. Max out at 100/10.
Sonic offers fiber in certain blocks of the Sunset, but are deploying painfully slow.
I have an ATT U-Verse box permitted to install on my block but it hasn't happened yet, and I'm not thrilled with ATT.
Monkeybrains requires LoS to Sutro tower, and permission from the building landlord.
Webpass requires at least 20 units in a building.
Google remains the only hope; build it, TAKE MY MONEY.
[1] http://www.fcc.gov/guides/over-air-reception-devices-rule
But the dominating factor of what determines where people live in the suburbs seems to be schools more so than internet. Google fiber here would be more of a novelty.