Robert Silverberg’s Gilgamesh the King. It’s a retelling of the Epic of Gilgamesh, with all of the supernatural elements either removed or given alternative natural explanations. I haven’t read it for a while, but I remember it as being pretty good.
Along those same lines, Mary Renault’s pair of books fictionalizing the life of Theseus, The King Must Die and The Bull from the Sea, are pretty good, but maybe a little more advanced civilization than you want.
Sam Barone’s Eskar Saga books are a fun read. Not great lit by any means but neat scenario. They are set in Mesopotamia just as villages are growing into cities. Disclaimer I’ve only read the first three.
This isn’t going to help much because I remember neither the author nor the name of the work, but it does seem to fall in the time frame you are interested in, and maybe this will trigger a memory in someone else.
A few years ago I read either a rather long story, or a short novel, set in the time when humans were moving from being hunter-gatherers to cultivators of grain. In it, a young woman from a hunter-gatherer tribe finds herself in a center of cultivation, like a small city with permanent buildings. In this city she observed that most people only ate mostly bread, and she thought everyone was pasty and unhealthy looking, compared to her tribe members. I don’t remember much past that, so I can’t even say if it was a good story or not. That premise just stuck in my mind. The author did seem to be sort of proselytizing for the paleo diet in a way, since he made consumption of grain products seem revolting.
James Michener’s “The Source”. It’s several stories contained in the framework of a story of an archeological dig in Israel in the 1950’s. Many artifacts are found at different levels, from an animal jawbone fitted with flints to a spent bullet from the 1948 War of Independence. The “inner” stories are stories about the people who lived at the various times and used/made the artifacts from each era.
Samuel Delany’s “Return to Neveryon” series is the first thing that came to my mind. It’s pretty literate and can be complicated, but one of its themes is the development of civilization, including the beginnings of (relatively) advanced technological and economic development and its effects on society. I remember a convincing argument being made that patriarchal societies only started taking over after the introduction of money and some other good stuff.
There are some slight fantasy elements (at least one dragon) but I wouldn’t let that turn you off of it if you don’t like that sort of thing.
Mary Stewart’s Merlin Trilogy, which are set in the period just after the Romans left Britain, and treat Merlin, Arthur and other characters as if they are real, historical humans without any magic.
First book is ‘The Crystal Cave’.
‘Last Of The Amazons’ by Stephen Pressfield, who wrote the book ‘Gates of Fire’ about the last stand of the Spartans at Thermopylae.
Set in the 5th Century BC.
Possibly ‘Mythago Wood’ might interest you. It is a fantasy novel but the premise deals with the evolution of historical figures and stereotypes into legend.
It’s set just after WWI, and involves a returned soldier who goes into a wood to search for his missing father and brother, only to discover that it is somehow a
repository for the truth behind ancient British legends.
Won a World Fantasy Award, and is by Robert Holdstock.
‘Bridge of Birds’ - another award-winning fantasy/fiction story set in ancient China, about a peasant and a disreputable scholar who have to solve an ancient mystery.
By Barry Hughart.
‘The Histories’ by Herodotus. This is the oldest surviving example of a historical record written by someone who saw things with his own eyes.
Written around 450BC, it details Herodotus’ journeys across the known world, the wonders he saw, and also the tall tales passed on to him
by other travellers. He’s been called The Father Of History and The Father Of Lies, but in the last few hundred years a lot of the amazing
things he described have been validated by archaeological and historical discoveries. The writing style of English translations is a bit much
for some, but it’s one of my favorite books, and one of the great, founding pieces of western literature.
If you’ve read Conan and liked it, did you try Howard’s other creation Solomon Kane? An exiled English Puritan, he travels to Africa and other
exotic locations where he encounters various semi-legendary opponents and obstacles. For example:
The city of Nineveh, cursed by God, which is a real place.
A biblical demon imprisoned by King Solomon in old testament times, etc.
A bloody African empire based upon a lost outpost of the Atlanteans.