You are perfectly right. Physics starts with an assumption about spacetime or a spacetime model. For physics to work in our sense the only thing you need is that there is a causality structure, i.e., there must be an idea about the directedness of time dividing the past from the future of an event (at least locally). If your physics book is as complete as Newton's principia it starts with this definition, often in Newton's words. He called it "absolute time" and "absolute space", which means that the spacetime structure is given once and for all. Nothing physically happening does in any way affect space and time.
Mathematically you have an oriented time axis, which can be represented by real numbers through setting up a clock of some kind. Along this time axis you have (at each time) an 3D Euclidean affine space. Defining an origin and three oriented axes, which provide a basis of the vector space of the affine space, you can describe any point in space as the position vector ##\vec{x}##, and thus an event is characterized by the time ##t## and the position ##\vec{x}## it happens. Any observer, no matter how he moves against such a reference frame, observes exactly the same time duration and spatial distance between two events (this is what Newton calls absolute space and absolute time).
The next postulate is Newton's Law of inertia (Lex I). In a modern mathematical way it says that there is a preferred type of reference frames, the socalled inertial frames, where bodies move with constant velocity as long as there is no cause (forces) that change this state of motion. So the Lex I just says that there exists an inertial frame and thus a whole set of inertial frames, all of which move with constant velocity against each other.
This sets the kinematics of Newtonian physics. Then come the two dynamical Laws (Lex II + III), and these are very tricky in their original form. From a modern point of view, it's easier, because we have assumed already a lot with setting up the kinematics. The spacetime structure together with the existence of an inertial frame defines the symmetries of this structure, and any dynamical law must obey (on a fundamental level) these symmetries, which is called the Galileo symmetry. There's nothing that singles out any point in time or in space. So the laws of physics must be the same no matter were you set up an experiment (translation invariance in space and time). It is also not possible to single out any direction in space (rotational invariance) and the physical laws do not admit to determine any kind of absolute velocity of the reference frame, i.e., in any inertial frame the physical laws are perfectly the same (invariance under Galileo boosts). Given this symmetries you can analyze the form of the possible laws, using Hamilton's principle of least action and Noether's theorem about the connection between symmetries and conservation laws. It turns out that then you get easily Newton's 2nd and 3rd Law. As a textbook that follows such an approach, see Landau&Lifshitz, vol. I.
