That's not what Newtonian physics says. Wikipedia is not a good source (and the galilean invariance page in particular seems to me to invite a number of serious misunderstandings). You need to actually look at a textbook on classical mechanics.
The "B" level answer to the general question you are asking is that there are only two really significant differences between Newtonian mechanics and relativity:
(1) Newtonian mechanics obeys Galilean invariance, and relativity obeys Lorentz invariance. Everything else about motion flows from that, and if you understand the implications of that, you can forget all about "absolute space" and the other things that are confusing you.
(2) In Newtonian mechanics, gravity is a force; in relativity, it isn't. That makes relativity simpler because it doesn't have to try to deal with the question of why objects don't feel gravity as a force, i.e., why objects moving solely under gravity are in free fall, weightless. In Newtonian mechanics this has to be dealt with by a special ad hoc assumption that gravity works different in this respect from all other forces. In relativity, the question doesn't even arise.
In particular, as far as choosing coordinates, inertial vs. non-inertial frames, etc., there is really no difference between Newtonian mechanics and relativity, other than the invariance difference above. In both cases, you can choose coordinates in which any object you like is at rest, but those coordinates might not be inertial; and if they are not inertial, additional coordinate artifacts will appear that do not have a straightforward interpretation as being caused by a "source" (these are called "fictitious forces" in Newtonian mechanics, but similar effects appear in non-inertial frames in GR).