But how does one achieve such proficiency at solving problems of such varying degree and explaining them so lucidly?
One of Norvig's first jobs was working for Margret Hamilton.
In two dimensions. It's hard to think of a better role model. On the other hand, Norvig left consulting when he left Hamilton and went into academia for a decade.
Which means Norvig spent the decade from his mid-twenties to his mid-thirties in an environment that valued the development of clear communications and valued the ability to teach.
Like anything, what seems to be magic isn't. Norvig sounds professorial because he was a professor during a critical decade of his career. Whatever wisdom he has, has come from the usual route: age. And I suspect his insights are mostly the result of experience like everything else.
To put it another way, if you want to be like Norvig, work hard and stay in school.
Good luck.