I'm not sure it's quite accurate to say they didn't discover natural selection. They tended to believe a lot of other nonsense, though, which made it difficult to fully realize the idea.
Aristotle considered something like natural selection but rejected it because it didn't otherwise fit his worldview (which was opposed to atomism). Here he considers selection and variation, although he doesn't mention heritability explicitly.
Why then should it not be the same with the parts in nature, e.g. that our teeth should come up of necessity--the front teeth sharp, fitted for tearing, the molars broad and useful for grinding down the food--since they did not arise for this end, but it was merely a coincident result; and so with all other parts in which we suppose that there is purpose? Wherever then all the parts came about just what they would have been if they had come be for an end, such things survived, being organized spontaneously in a fitting way; whereas those which grew otherwise perished and continue to perish, as Empedocles says his 'man-faced ox-progeny' did.
Yet it is impossible that this should be the true view... action for an end is present in things which come to be and are by nature.
Source is http://classics.mit.edu/Aristotle/physics.2.ii.html, part 8. The reference to Empedocles is talking about http://en.wikipedia.org/wiki/Empedocles#Cosmogony, who arguably came closer, but it sounds like he had some pretty strange ideas about the origins of things. Anyway, I'd suggest that incorrect (scientific and metaphysical) beliefs were at least as problematic as lack of imagination in this case.
I don't know too much about Greek philosophy, though, so I'd be interested to hear someone explore this further.
A later atomist, Lucretius wrote about this in more detail. A translation is here you'll want to ctrl-f for his section on the origins of vegetable and animal life. His position is much like that of Empedocles.
I don't see why these wouldn't count as coming up with the idea of natural selection. They obviously lacked any understanding of genetics or how heredity functions. They didn't have the particular example of the Darwin's finches to illustrate fine-grained evolution-- but Lucretius is talking quite explicitly about about fitness and survival as an ex...
Also see: History of the Friendly AI concept.
The ancient atomists reasoned their way from first principles to materialism and atomic theory before Socrates began his life's work of making people look stupid in the marketplace of Athens. Why didn't they discover natural selection, too? After all, natural selection follows necessarily from heritability, variation, and selection, and the Greeks had plenty of evidence for all three pieces. Natural selection is obvious once you understand it, but it took us a long time to discover it.
I get the same vibe from intelligence explosion. The hypothesis wasn't stated clearly until 1965, but in hindsight it seems obvious. (Michael Vassar once told me that once he became a physicalist he said "Oh! Intelligence explosion!" Except of course he didn't know the term "intelligence explosion." And he was probably exaggerating.)
Intelligence explosion follows from physicalism and scientific progress and not much else. Since materialists had to believe that human intelligence resulted from the operation of mechanical systems located in the human body, they could have realized that scientists would eventually come to understand these systems so long as scientific progress continued. (Herophilos and Erasistratus were already mapping which nerves and veins did what back in the 4th century B.C.)
And once human intelligence is understood, it can be improved upon, and this improvement in intelligence can be used to improve intelligence even further. And the ancient Greeks certainly had good evidence that there was plenty of room above us when it came to intelligence.
The major hang-up for predicting intelligence explosion may have been the the inability to imagine that this intelligence-engineering could leave the limitations of the human skull and move to a speedier, more dependable and scalable substrate. And that's why Good's paper had to wait until the age of the computer.
</ speculation>