You mean like an age that saw the birth of the university and that had scientific and philosophical minds like Occam, Grosseteste, Anselm of Canterbury, Albertus Magnus, John XXI, Roger Bacon, Thomas Aquinas, Avicenna, just to name a few? A period where such a complex architecture as the gothic style emerged and culture flourished under Giotto, Dante and Petrarch?
Then the Late Middle Ages is exactly what you are looking for!
Just Google "Medieval renaissance". No serious historian still clings to the outdated model of the Dark Ages. The Middle Ages are not monolithic and there are several medieval periods where intelectual and "scientific" inquiry (at the time it was natural philosophy) were prevalent.
EDIT: Let me add some points to my answer, so as to address your specific points on the comment section:
1) Belief in science
At the time of the Middle Ages there was not science as defined today. But there was such a thing as natural philosophy. Likewise, there was no scientific method per se, but the Middle Ages saw the birth / rebirth of a kind of empiricism that was the undeniable embryo of Enlightenment's scientific method.
European precursors to the scientific method are Grosseteste and Roger Bacon. On the muslim side, you have Alhazen and Avicenna. All these proposed a kind of empiricism that really isn't so far away from modern scientific method.
It really isn't too farfetched to have people on your world "believing in science" by using a kind of Roger Bacon empiricism. Really.
2) Belief that "we don't know"
If you mean the humbleness that scientific etiquete demands (i.e. "we need more evidence to assert this hypothesis") or the belief that knowledge grows steadily and assymptotically, then I think that the Middle Ages are more prone to that than prideful Enlightenment's positivism.
Medievals (either christian or muslim) believed that knowledge derived from God, who had created the World with reason and measure. But God is also unfathomable. Religious people at the time gasped with a sense of Mistery that came from God, the ultimate source of Truth. There was humbleness and awe... puny mortals just "didn't know everything". It was unthinkable to have mad scientists trying to become god-like or technological hubris leading to a kind of distopia.
3) Rich people (other than lords) spending time in art and philosophy
The Middle Ages also saw the birth of the burgeosie. For the first time, commoners could become wealthy and access the great treasures of culture. Why wouldn't they spend time in art and philosophy?
If you want the knowledge to trickle down to even lower strata of society, then research the Carolingian schools. It is not farfetched to create a medieval setting where learned clerics teach the children of peasants the basics of reading and mathematics in monasteries or churchyards.
If a peasant was particularly gifted, he could receive a grant to study at a university. That's what Pedro Hispano is thought to have done, until he became a physician, one of the leading scholars of the time and finally the pope.
4) Debate on religious topics allowed with little reprisals
This was actually quite common. Let me introduce you to Scholasticism, where people are encouraged to ask questions, and analyse every possible answer to them, even heretical answers. The scholar should formulate hypotheses by posing them as questions. He should analyse every argument pro and con and ponder every angle and perspective. Only then would he select an answer and justify it. He would even be encouraged to find sintheses between apparently contradictory statements.
Oh, and if you didn't agree with someone, even regarding arguments about faith, you could only refute your detractor by using his best arguments, posed as they were really meant to be exposed. No spinning of contrary arguments and no logical fallacies were allowed. Even heretics received this honorable treatment.
So Thomas Aquinas ponders on his Summa Theologiae whether God exists or whether Christ resurected from the dead, and gives arguments against these dogmas before making up his mind.
Sure, this was only at a theoretical and intelectual level. In real life, you could not hold a heretical belief against the established religion, because religion was at the time a matter of State. There were inquisitions at the time, and pogroms, and religious persecution to the Cathars (though what we decry nowadays as Teh Inquisition is more a product of Renaissance than of the Middle Ages). However, those are acidental, not neccessary for a medieval setting. Just handwave away the "cuius regio eio religio" and the inquisitions and you'll get what you want.
Need examples? Search how during some kings, the Iberian Peninsula was a haven of religious tolerance between the Three Great Monotheistic Religions.
Need my help to imagine a plausible scenario for the handwave? Just change the Magna Carta story to fit what you want. Put the barons rebelling, not against a Prince, but against a Bishop (there were several of these rebellions anyway), and make them demand religious tolerance instead of freedom from abuse of kingly power.