Maybe a key part of what's missing in your understanding is not so much "micro" genetics but biogeography and population genetics. You'd also want to check simulations and comparisons with real-world data on some models to see how a population evolves to see that it "really works". It's important to understand that there are different models, and for each one there's a set of "forces" and important parameters.
The bigger picture is, it's the whole interplay between mutation, selection, genetic drift, gene flow; things like differences in population size over time and space, migrations, isolation and reconnection, etc. that makes it work. You might also want to take a look into genetic/functional/morphological modularity. I've just skimmed these articles, but they seem relevant:
https://www.nature.com/articles/hdy2010136
https://www.nature.com/scitable/knowledge/library/natural-se...
There's much more but my memory is murky. Ideally you would want to take a course or read a textbook on evolution. A few popsci books are ok (Dawkins, E. O. Wilson).
TLDR: What the other commenter said -- 4 billion years is a very, very, very long time.
The last I ever learned about it, and perhaps the common belief, is that random-ish gene mutations account for it. 4 billion years doesn't seem like enough time to account for all that unless changes are heavily weighted towards doing something somewhat useful. Like there is a system at play.. Lego blocks vs bits. IDK.