From production through distribution, oil and gas infrastructure provides the largest source of anthropogenic methane in the United States and the second largest globally. Using a Picarro G2132i Cavity Ring-Down spectrometer, we mapped natural gas leaks across the streets of three United States cities - Durham, NC, Cincinnati, OH, and Manhattan, NY - at different stages of pipeline replacement of cast iron and other older materials. We identified 132, 351, and 1050 leaks in Durham, Cincinnati, and Manhattan, respectively, across 595, 750, and 247 road miles driven. Leak densities were an order of magnitude lower for Durham and Cincinnati (0.22 and 0.47 leaks/mi, respectively) than for Manhattan (4.25 leaks/mi) and two previously mapped cities, Boston (4.28 leaks/mi) and Washington, DC (3.93 leaks/mi). Cities with successful pipeline replacement programs have 90% fewer leaks per mile than cities without such programs. Similar programs around the world should provide additional environmental, economic, and consumer safety benefits.