This question is really about history and what was known to the protagonists in your tale and at what time. As a principle, relativity was embraced every bit as fully by Newton and Galileao as it was by Einstein - it's just that Einstein had a few more experimental results he had to gather into relativistic thinking.
As in dgh's answer the whole point of special relativity is that velocity is a relative concept insofar that the physical laws will seem the same to all inertial observers.
This concept was well appreciated by Galileo and Newton. See for example the quote of Galileo's character Salviati in the Galileo's Ship Thought Experiment of 1632. Saviati's narrative is clearly saying that there is no experiment whereby one could tell whether or not the ship were moving uniformly.
So, in spirit, Galileo's and Newton's physics were no less "relative" than Einstein's. The problem is that there is no unique way to make physical laws the same for all inertial observers. See the derivation of the Lorentz transformation under the heading From Group Postulates on the Lorentz Transformation Wikipedia Page. Here the Lorentz transformation is derived from very basic symmetry and homogeneity assumptions about the Universe. Take heed that the derivation only yields the form of the transformation, it does not yield the universal speed parameter $c$. So there are a whole family of relativities that fulfill these basic symmetry and homogeneity assumptions - roughly that physics is the same for all uniformly moving observers - and both Einstein's special relativity and Galilean relativity belong to this general family; the latter is simply the limit as $c\to\infty$.
Not to detract from Einstein's achievement, Einstein was responding to experimental results not known to Galileo and Newton - namely that speed of light seemed to be constant for all inertial observers - and showing that, against intuition at the time, this observation could still be consistent with the principles of inertial invariance of physics so clearly stated by Galileo's Salviati. It's simply that the reference frame transformation laws had to be different. To Galileo and Newton, the transformation laws implied by inertial invariance would have seemed to be unique; Einstein simply disproved this and showed instead that there was a more general transformation. That transforamtion challenged to notion of absolute time and simultaneity. This was the leap that revealed the non-uniqueness of Galilean relativity, which is indeed unique if one insists on upholding the notion of absolute time. Einstein's physics is "more relative" than that of Galileo and Newton, but only by dint of experimental results. These results forced the forsaking of a principle that Galileo and Newton had no experimental grounds to forsake - that of absolute simultaneity and time.
