(1) Page and Brin started Google Inc successfully in SV so it seems contradictory to advise others not to start a company there
(2) the meaning of the word "start" as Brin is using it
As for (1), Larry and Sergey had the luxury of building Google (the product -- not the formalized "incorporated" Google Inc) inside of Stanford and therefore using the university's computers and bandwidth for free. Piggybacking on Stanford's resources to create an "mvp" was like getting "AWS" for free. A lot of startups don't have that situation. Therefore, a founder may be better off working out the parents' garage in Kansas to keep expenses low. The free room & board is money that would have been spent on a crappy apartment in SV. Instead take those savings and use it to pay for the AWS hosting costs, or a 2nd programmer.
For (2), I think Brin is talking about "start" as in start from zero with an idea on a paper napkin, before an MVP, and before traction from others (users and investors). Zuckerberg started Facebook in Boston and after Sean Parker got interested, he moved Facebook to the more expensive SV. Bill Gates started Microsoft in Albuquerque, New Mexico and made profits before he moved the company to the more expensive Seattle. In other words, you can have a "low profile startup" in your local town that's under the radar which lets you keep expenses very low. You can later have a "high profile startup" in Silicon Valley where the very high costs are worth it to hire from the talent pool and network with other entrepreneurs and investors. That delayed move to SV is what Brin called "that second step".