How about public transport you can take the bikes with you on, and nice bike paths in the denser areas?
The main issue isn't just roads its and entire infrastructure, e.g. giving bikes priority over motor vehicles like in some European countries which might not work well, In many cases bike lanes tend to also have a negative impact as they are often take spaces from public side walks, you can see that being a very big issue in some European cities that went bike crazy.
London is trying to do that and it's infuriating bikes seem to do what ever the fuck they want they'll go in the bike land but on a red signal they'll decide to go over the cross walk and onto the side walk to get a head, they often go into red signals even on the road when there is no (or they think there isn't) incoming traffic, and they clog bus lanes.
You can't just go from 0 to 60, turning SV into a bike friendly zone will take as much time as it took to turn Copenhagen or Amsterdam into one.
Do you have a citation for bike lanes digging into sidewalk? I've literally never heard of that, especially in the US where sidewalks are never near bike lanes and separated by a curb/parking/grass.
A better rack design (hanging vertically on the rear?) could solve this.
You say "you can't just go from 0 to 60". That applies to bike culture too. As the segregated lanes are put in, London's cycling culture will become calmer, just as it is in Copenhagen or the best Netherlands cities.