That was indeed the state of the art in Galileo's time. Heliocentrism wasn't necessarily more elegant, because it left open problems such as why people don't fly off the earth, and why the oceans don't slosh around uncontrollably. From what I've read, the Church was prepared to accept the model of Tycho Brahe, in which the sun goes around the earth, and the planets around the sun, which is yet another equivalent view within that conception of reality.

Newton gave us a couple of things. First, as you say, he gave us a model of gravity. Secondly, he gave us the framework within which to test whether the earth is rotating or not, e.g., through observations of things like Foucault's pendulum, and the Coriolis force.