I agree, evolution's scale is colossal, but restrict your view to the tiny bit of the evolutionary machine that is implicated in figuring out how to arrange neurons (which evolution "discovered" previously, to be fair, with incredible effort) in a fashion that renders their behavior intelligent, and it becomes a vastly smaller effort.
These beings are all rather large, at least worm-sized or greater. Their lifecycles are measured in days to years, not minutes or hours. And they only had 250 million years or so to make the leap from "bunch of neurons hard-coded to do specific jobs" to "generally intelligent arrangement of neurons capable of higher level thought". All of this cuts the scale by at least 5-10 orders of magnitude compared to what you correctly point out as the overall colossal scale of evolutionary computation. And to me, it says that compared to all the other amazingly difficult stuff that evolution has discovered, intelligence was a damn easy find, especially since there's almost no fitness benefit - hell, worms probably do better than we do as far as evolutionary fitness goes, they're tiny, numerous, and reproduce like crazy.
My money is on the fact that human intelligence guiding a search cuts another couple orders of magnitude off of how much of a long-shot discovering an intelligent algorithm would be via a random search. I could definitely be wrong, it's very hard to be precise when you're vaguely arguing about orders of magnitude, but to me it doesn't seem like the algorithmic "magic" in the brain can possibly be very complex if evolution was able to get there, there just aren't many other circumstances where evolution stumbles on something that damn clever.