If the state of natural science instruction were the same as the state of theological instruction not everyone would believe in gravity either, and those who would believe would dispute the particulars. Examples: flight observationally contradicts gravity; the fact that all objects fall with the same acceleration observationally contradicts gravity. The medieval man would have found a belief in God far easier than belief in Newtonian gravity.
Flying does not contradict gravity. Anything that flies does so temporarily, as long as there is active force involved to counter gravity.
Equal acceleration is observed in vacuum. I doubt that it was known to anyone in the Midle Ages. They would surely think a rock would fall faster than a feather -- and that is true as long as the effects of air resistance are present.
A medieval man would have no problems accepting gravity. He knew just as we do that jumping off a great height is not a good idea. He accepted God on authority of the Church.