Actually, the moths example is a fake. The photos were shown to have been staged.
But this does not mean evolution is a fake at all. Evolution is very, very real - you have, I am sure, heard of fossils.
As in horses, there's an example. Horses started off about the size of moderate-sized dogs. They had four or five toes. Little things, probably cute. Then, as time went on, horses that ran faster were more likely to survive to breeding age and reproduce. Those horses tended to have three toes that hit the ground, and the other one or two hung to each side (much like a dewclaw on a dog). These horses were also larger, with longer legs. So the four- and five-toed horses could not compete for food and mates, or they just didn't live too long, as predators were more likely to catch them. Then, even bigger horses, with longer legs, started to appear, due to genetic mutation. They could run faster than the smaller horses. And, they had one large toe with two others hanging on either side. So these horses were more likely to survive to breeding age. And the smaller horses began to die out. Finally, a genetic mutation resulted in a horse being born with only one toe, with a large toenail which we call a hoof. That horse was the largest of them all, with long legs and a quick stride. That horse was most likely to survive to sexual maturity. It could eat more grass, kick at and outrun many (but not all) predators, and live long enough to breed and pass on its genes to a new generation. Hence, it survived while slower, smaller horses did not. Now, I'm simplifying matters. It wasn't that perfect or in as straight a line as that, but it did happen.
See:
http://www.talkorigins.org/faqs/horses/horse_evol.html
By the way, science and religion are vastly different things. Science should not be used to try to "disprove" religion any more than religion should be used to try to "disprove" science. There's room in the world for both, so long as we don't confuse one with the other.