One thing that a really bugs me about evolution is the gradual changes
what benifits does that bird-lizard animal have in between transforming?
Or did it just suddenly pop into another animal?
Evolution isn't necessarily about making a population of organisms better at fighting, flying, breathing fire, etc. It's about making them more suited to the environment they live in so that they reproduce more. Say that there was a wet-spell and all the trees grew in a forest, and so all the food was higher up in the air. The bird-lizards that hold the genes for bigger wings can fly higher and get the food. The bird-lizards that don't have the genes for bigger wings can't fly high enough to get the food and more of them starve. So what ends up happening is that the big-winged bird-lizards end up surviving long enough (on average) to mate and have more baby bird-lizards, and so gradually you end up with a group of bird-lizards that don't have any more small-winged bird-lizards because it was naturally selected out of the population.
So in short, the important thing to note is that 'fitness' doesn't mean stronger or better, it just means more suited for the environment that the population lives in.
EDIT: I think I completely misread your question. There's a lot of differences in the environments between the cretaceous period and the modern day Earth. You can read about some of the driving environmental stresses for wing-development by reading about Archaeopteryx and other species that people call the 'bridge' between dinosaurs and birds.