The standard text on the subject is I. F. Clarke’s The Pattern of Expectation: 1644-2001, published in 1979.
Chapter I is “The Discovery of the Future,” in which he presents a number of candidates for first future fiction. As with most things the genre took a while to evolve into a form we would recognize, so you get to pick which book satisfies your criteria.
Aulicus his Dream, of the Kings Sudden Comming to London, by Francis Cheynell.
A six-page tract in the form of a dream, a nightmare vision of King Charles triumphant in London.
Epigone, histoire du siecle futur, by Jacques Guttin.
Set in a future France with a vast kingdom but just as a backdrop to a adventure story.
Memoirs of the Twentieth Century, being Original Letters of State under George the Sixth, by Samuel Madden.
A future in which Britain is powerful and the Catholic countries are not.
The Reign of George VI, 1900-1925, anonymous.
Another English utopia because of enlightened British wisdom.
L’An 2440, by Sebastian Mercier.
The biggie. “The first satisfactory model of the new fiction.” A “detailed utopian account of peaceful nations, constitutional monarchs, universal education, and technological advances.” The book was wildly popular, went into many printings, and was translated in several other languages.
Clarke lists dozens of other books pre-Verne.
A more recent source of early speculative writing is The Encyclopedia of Fantastic Victoriana, by Jess Nevins, which starts much earlier than Victoria, despite its name. He evidently has done research into scads of forgotten magazines of the late 18th and early 19th century to uncover much that is new to us.
Why didn’t it appear earlier? I think it was because it wasn’t necessary. Writers had been pounding out such yarns for thousands of years; they just set them in the unexplored sections of the world, where any wonders were plausible.
Most say that the founder or at least forerunner of science fiction was the True History by Lucien of Samosata, circa 150 AD.
I love the very free translation of the intro by this author:
It wasn’t until most of the earth had been explored and found to be inhabited by humans much like the travelers that there was a need to find an “other” place in which to set these tales in. The future was a convenient device, because unlike the tales set in China or the Indies, nobody could go there and report back the reality.