To get this discussion back on track...
What do you guys think is the earliest that evolution could have been discovered, or at least hypothesized?
As others have already noted, some early theorising about this was done already in antiquity. One needs to keep in mind it was theorising - mostly without the study of fossils and other material remnants, etc. - and not a generally accepted scholarly opinion at the time. And given the wide acceptance of the ideas of early scientist-philosophers such as Aristotle - who believed in a very folksy and now-unscientific form of abiogenesis (i.e. fleas forming from grime, fish from water, etc.) - you might see a more recognisibly modern thinker from antiquity overlooked or forgotten in favour of the more publicly famous scholars of the period.
I would assume a working theory of evolution would have to include the following observations/conclusions, but please correct me if I'm wrong
All your points are sound, they just need elaborating upon.
There's a reason why more empirical study of fossils and evolutionary processes took a while to develop in the history of science. You might have people theorising about evolution already in Antiquity, or the Middle Ages, or early modern times, but much like with inventing the steam engine, what's often missing is a good constellation of existing knowledge, new methods, new findings, etc., to create a perfect storm for a paradigm shift in the natural sciences most closely linked to studying evolutionary processes.
- that diverse organisms are related in some way, and not just isolated immutable "kinds" as in Young Earth Creationism
This is one of the breakthroughs needed for the understanding of extinct ancient life. If naturalists are still largelly convinced that species have largelly been the same since time immemorial, and more bizarre-looking finds are just "natural curious", then you can have individual researchers formulate evolutionary theories all you want, they might get overlooked at the time. What is needed is a perfect storm, where the consensus among period researchers has shifted to accepting the idea that "ancient life might have been very different to present day life on Earth".
- that there existed organisms in the past that don't exist today, and vice versa
IIRC, in OTL, the long-held explanation was that fossils were bones of mythical or unknown creatures (the latter technically right), later that they were tricks of nature (in the sense of pareidolia), then that they were victims of the biblical Flood, and finally, that they were victims of ancient
local catastropes (geological and other).
Also, there were cases of misidentification, even in the period when naturalists started entertaining the idea that these are remnants of ancient life. The fossil of a large prehistoric amphibian,
Andrias scheuchzeri (nowadays in the Teylers Museum in Haarlem, NL) was confused by 18th century Swiss scholar Johann Jacob Scheuchzer for a member of some vanished, pre-Biblical flood race of diminutive people. This was in 1726, less than a century from Lamarck and co.
The whole "biblical flood wiped these ancient creatures out" narrative was very popular for a long time, even when naturalists started studying fossils more seriously, and less as "strange curios". Even at the time Scheuchzer came up with his bizarre explanation, other naturalists and scholars were already coming up with less outlandish explanations for discovered fossils, but were obviously missing the conclusion of just how old these were. By the early 19th century, the "one-time biblical flood behind everything" explanation became untennable.
Catastrophism came into vogue as a more scientific explanation, but was clearly rooted in the still limited knowledge of the time. Catastrophes as movers and shakers, but decpited and thought about as always analogous to those known from human history, just larger. Cuvier, who you've mentioned, was a major populariser of the catastrophism thesis among early paleontologists. Wegener's tectonic plates discovery was still a century away, and even though the 19th century saw gradual sophistication in the ideas about the extinction of species, biologists of the time still had a much rougher idea about what natural mechanisms contribute to changes in environments*, extinction and evolution.
(* - besides the bleeding obvious, such as volcano erruptions and such, part of why catastrophism was a concept narrowly focused on a "local catastrophes" understanding of evolutionary processes. Once you grok that things like plate tectonics exist, you start getting a much clearer picture of why certain species were found where they were found. Geographic connections and similarities between extinct species not explainable as convergent evolution no doubt seemed baffling to scientists in a time before plate tectonics were acknowledged.)
- that organisms are affected by random internal changes, whether recognized as being connected to heredity of traits, or more directly to chemical changes in the most basic substance of organisms
This will be important, but without a deeper scientific understanding of said processes, it won't develop as soon as you'd hope. The benefit of hindsight is a big issue when thinking about these ATL developments. A similar thing tends happen when we're bewildered why people from a certain didn't develop a now-mundane simple piece of technology sooner. Hindsight can be very deceiving in alternate history, and it's tempting to put the cart before the horse. Until relatively recently, heredity was understood only vaguely. We knew it happened, we realised some of the principles behind it, but it wasn't really until the mid 20th century when we started cracking what's behind it on an internal, biochemical basis. Evolutionary genetics would be a tall order for any earlier-than-OTL discovery of evolutionary principles in nature. You'd get Darwin or Mendel level efforts first, especially if our hypothetical ATL breakthrough happens in the medieval or early modern period, centuries before the OTL scientific revolution. Mind you, people have understood heredity to some extent for thousands of years (hence breeding of animals, or the creation of plant cultivars), it's just that the principles behind that heredity seemed like "a mystery of nature" to most people until the last 200-300 years of OTL, when we started getting a better idea of what heredity actually is, which in turn led to the gradual creation of genetics as a research field.
- that the nature and prosperity of organisms is somehow tied to the conditions and environments they live in
This is one of those big discoveries that will form part of the gradual paradigm shift towards a far more in-depth understanding of ancient life, and subsequently, the understanding of evolutionary processes as well.
People like Carl Linnaeus and Georges Cuvier were already hitting on some of these points before Darwin, but not hugely before. Was it possible for these interconnected observations/conclusions to have been discovered in the early Modern period? In the Middle Ages? In the Islamic Golden Age? In Antiquity? Why or why not? And what would have been its effect on human knowledge and scientific progress?
My own conclusion is that it's certainly not impossible, but you need to have (at least in some aspects) a roughly similar conflusion of science, study and a whole cultural/economic backbone for naturalists as serious scientists, with corresponding academic and cultural status, as in OTL. If naturalists will still be seen as half-wacky alchemists and metaphysical philosophers by society at large, then even the ones who come close to formulating a mostly-correct evolutionary theory might be ignored. One of the key things that needs to happen earlier is the development of
the scientific method, as we understand it today. It doesn't have to be the perfect, fully-formed thing already, but it should at least have some of the basic principles of the method. Evolutionary theory needs to be developed on both an empirical basis and a theoretical basis. If most scholars from ancient periods only approach evolution as a theoretical possibility, as a hypothesis (without actual study of the material evidence), then other period scholars can easily dismiss their ideas, consider them "just another theory, not necessarily true" and so on.
So, the scientific method
is really needed here, even if you get an earlier breakthrough for it - say, 3 centuries earlier than OTL, to give an example off the top of my head. The fully-formed scientific method being developed earlier would have further major impacts on all other sciences, culminating in numerous ATL developments, but looking purely at paleontology et al. Evolutionary research rooted in the scientific method can't be dismissed as "philosophical ramblings" of one or two scholars, but as stuff that's genuine science and genuine research with a lot of effort put into it (in the field and the lab, as well as behind a desk). The scientific method helps it attain a leap from "theorising / speculation" to "doing science".
Anyway,
this collection of PODs might interest you.