> Our big brains didn't pay off for millenia, until they did, and in a big way.

That's not how evolution works. Each step along the way must produce a net benefit or it gets discarded. Just as insect wings served as propulsion for water skimming before actual flight, big brains paid off, then got bigger and paid off some more, etc. The only hiccup is the benefit has to outweigh the cost (eg big brains need more calories).

Side note: I think our wide array of modern mental disorders are costs of our brains' continuing enlargement. I.e. brains are trying to figure out how to get even bigger and more powerful without also having OCD or schizophrenia.