In an essay called "The Reception of the 'Origin of Species'" printed in Life and Letters of Charles Darwin (and reprinted in Life and Letters of Thomas Henry Huxley), "Darwin's Bulldog" T.H. Huxley described the intellectual shock of understanding Darwin's theory of evolution by natural selection;
As I have already said, I imagine that most of those of my contemporaries who thought seriously about the matter, were very much in my own state of mind -- inclined to say to both Mosaists and Evolutionists, "a plague on both your houses!" and disposed to turn aside from an interminable and apparently fruitless discussion, to labour in the fertile fields of ascertainable fact. And I may therefore suppose that the publication of the Darwin and Wallace paper in 1858, and still more that of the "Origin" in 1859, had the effect upon them of the flash of light which, to a man who has lost himself on a dark night, suddenly reveals a road which, whether it takes him straight home or not, certainly goes his way. That which we were looking for, and could not find, was a hypothesis respecting the origin of known organic forms which assumed the operation of no causes but such as could be proved to be actually at work. We wanted, not to pin our faith to that or any other speculation, but to get hold of clear and definite conceptions which could be brought face to face with facts and have their validity tested. The "Origin" provided us with the working hypothesis we sought. Moreover, it did the immense service of freeing us for ever from the dilemma -- Refuse to accept the creation hypothesis, and what have you to propose that can be accepted by any cautious reasoner? In 1857 I had no answer ready, and I do not think that anyone else had. A year later we reproached ourselves with dulness for being perplexed with such an inquiry. My reflection, when I first made myself master of the central idea of the "Origin" was, "How extremely stupid not to have thought of that!" [emphasis mine]
Natural selection had already been discussed prior to the publication of Darwin's book, most notably by William Wells, Patrick Matthew, and Edward Blyth, but simple priority is not enough to shift credit away from Darwin and Wallace for sparking a scientific revolution. Wells was the first of the three, noting that just as different breeds of animals could be created through artificial selection so could nature adapt humans to different parts of the world through the selective pressure of climate and disease. The paper was read in 1813 but not published until five years later by which time Wells had died.
Matthew came next, his 1831 book On Naval Timber and Arboriculture containing a relatively brief explication of how natural selection might change organisms over generations. Matthew's notion was more general than Wells' but he did nothing to further develop the idea. His explication of natural selection was sunk into a book on growing trees for shipbuilding, and although Darwin later recognized Matthew's priority (Matthew feeling cheated that Darwin didn't know of his work and give him credit) Matthew doesn't seem to have played any further role in establishing natural selection as the prime mechanism for evolutionary change.
Blyth is the latest of the trio that are often said to have anticipated natural selection, publishing several articles on the subject between 1835 and 1837, but his view of the process ran counter to that of Darwin & Wallace. Rather than creating new species natural selection returned animals in nature to their archetype, a sort of evolution in reverse. Although Blyth grasped part of the idea he ran in the wrong direction. (Stephen Jay Gould wrote a much more detailed essay on the various claims to priority and the details of each different system of natural selection, which can be viewed here.)
Hindsight, of course, is 20/20, but even though the question of the "origin of species" was hanging over the heads of 19th century naturalists the "secondary law" that would solve the problem remained elusive. Reliance on Scripture to provide an accurate history of creation had ebbed away to almost nothing, and while religious sensibilities still influenced geologists & zoologists there was no longer a way to reconcile the evidence from the natural world with a literal reading of the Genesis narratives. Richard Owen, rather than being a young-earth creationist as many whiggish history summaries make him out to be, was working on this problem himself and accepted evolutionary change; he just didn't accept Darwin's theory. Owen's phrases like "the continuous operation of the ordained becoming of living things" are more confusing than helpful in determining just how he thought new forms arose, but it is clear that he (like many others) were certainly concerned with the problem of origins.
When Darwin did publish On the Origin of Species by Means of Natural Selection in 1859 it finally provided a reasonable mechanism for evolutionary change. "Reasonable" does not mean "universally accepted," however, and while the book was often admired many still had reservations. Reasons for this are various, one of the most prevalent being that natural selection was too brutal a mechanism, but many felt that there were scientific reasons to doubt Darwin. During the time that Darwin was writing paleontology was a relatively new science, yet many paleontologists felt that the earth's strata had been sampled adequately enough to provide a clear picture of the succession of ancient life. This was problematic for Darwin as his theory predicted a finely graded chain of intermediate forms connecting all life together, gradations that were missing. Darwin appealed to the notion that the fossil record was riddled with holes and the unlikelihood that intermediates would be fossilized, but the consensus of paleontologists at the time was in direct opposition to this appeal. If the geologic succession of time periods could be accounted for without major gaps then nearly all of ancient life could be accounted for, the lack of transitions between forms refuting Darwin's prediction of common ancestry.
This general attitude is summarized in John Phillips' book Life on Earth. Published in 1860 it is one of the earliest books to compare Darwin's predictions with the evidence from the fossil record, finding value in Darwin's efforts but ultimately rejecting his evolutionary program. One example that Phillips uses is the seemingly sudden emergence of life on the oldest known strata at the time, the Cambro-Silurian system. According to his argument that fossils in these strata are so delicately preserved that whatever there was to be fossilized certainly did so, thus throwing doubt on the discovery of any potential ancestors of forms in later periods. Likewise there were no fossils known from older rocks, and if there were no progenitors then the continuity of life that Darwin's theory predicted is broken. The theme is nearly ubiquitous throughout geologic time, Phillips argues; there are plenty of related forms in different periods but no conceivable links to connect the groups together.
Influenced in no small way by natural theology, Phillips finds natural selection wanting on nearly all counts, concluding;
It may be thought that, while professing to keep to the old and safe method of reasoning on known causes and ascertained effects, we deviate from this principle in regard to the origin of life, and introduce an unknown cause for phenomena not understood, by calling to our aid an act of 'creation.' Be it so, let the word stand for a confession of our ignorance of the way in which the governing mind has in this case acted upon matter; we are equally ignorant in every other instance which brings us face to face with the idea of forces not manifested in acts. We see the stream of life flowing onward in a determined course, in harmony with the recognized forces of nature, and yielding a great amount of enjoyment, and a wonderful diversity of beautiful and instructive phenomena, in which MIND speaks to mind. Life through many long periods has been manifested in a countless host of varying structures, all circumscribed by one general plan, each appointed to a definite place, and limited to an appointed duration. On the whole the earth has been thus more and more covered by the associated life of plants and animals, filling all habitable space with beings capable of enjoying their own existence or ministering to the enjoyment of others; till finally, after long preparation, a being was created capable of the wonderful power of measuring and weighing all the world of matter and space which surrounds him, of treasuring up the past history of all the forms of life, and of considering his own relation to the whole. When he surveys this vast and co-ordinated system, and inquires into its history and origin, can he be at a loss to decide whether it be a work of Divine thought and wisdom, or the fortunate offspring of a few atoms of matter, warmed by the anima mundi, a spark of electricity, or an accidental ray of sunshine.
Such rhetoric makes it clear that the pull of natural theology was still strong in 1860. Each organism is "appointed a definite place" and either enjoys its own existence or "[ministers] to the enjoyment of others." Humans, of course, preside over all, the diversity of extant and extinct life being meant to serve us and remind us of our place in it. Indeed, while Phillips may have been open to a secondary law to govern the formation of species he saw Darwin's theory failing on both scientific and philosophical grounds, with religious sentiments making it further impossible to accept a system that closed the doors on divine intervention.
If there is any controversy that should be taught about evolution in classrooms it is that the victory of natural selection as the central evolutionary mechanism was hard-won. Nearly 100 years ago, when the 50th anniversary of the publication of On the Origin of Species was being celebrated, evolution was widely recognized but the mechanism by which it did so was still highly contested. Darwin's idea is surely powerful, undeniably so, but it did not sweep through Western society like a shockwave making immediate converts of all. Some people accepted it, many others vehemently disagreed, but if nothing else Darwin's work spurred a greater interest in solving the question of origins. Whether it was to prove him right or wrong there was a flurry of work and debate that began in 1859 and has been going ever since. Even if Darwin turned out to be wrong, if some other evolutionary mechanism deserves primacy of place, On the Origin of Species would still deserve wide recognition. It moved naturalists into action and changed the way we see ourselves, and that alone is certainly worthy of recognition.