> For Nature to learn how to develop a nervous system capable of flexibly interacting with the environment, culminating in our brains, took hundreds of millions of years.

Nature never learned anything. Nature is not a force that chooses what features it wants to implement in living things. We evolve in periods of punctuated equilibrium, when the average individual within a population cannot reproduce successfully. Then species change very quickly(sometimes sub-1000 years) to fit their environment. We're not sure why humans evolved to be so intelligent, but one possible reason is that our environment was changing very quickly, so quickly that we had to change our core behaviors within the course of a life time.

It can be very confusing to anthropomorphize Nature. Since Nature never tried to make intelligence, the speed at which intelligence evolved in Nature is pretty irrelevant to the difficulty of the problem of intelligence.