Well, you can be sure, quantum theory is much more mind boggling than classical (classical=non-quantum here) relativistic physics.
Nowadays we are pretty used to high-precision time keeping, i.e., nearly everywhere we have some standard time available. This is provided by the national bureaus of standard nearly everywhere on the world and practically awailable in many forms, e.g., by ntp servers for your computer or the GPS etc.
This is, however by far not a trivial thing! In Einstein's time, around 1900, every city had its local time. Maybe that's why Einstein came to his clock-synchronization idea to address the problem of finding a spacetime compatible with (a) the principle of inertia (i.e., the (apparent) existence of a special class of reference frames, where Newton's principle of inertia holds) and at the same time (b) Maxwell's equations, describing electromagnetic phenomena.
First of all one cannot overemphasize the importance of the paradigm change Einstein brought into the thinking of physics: Before, everybody took the Newton-Galilei space-time model as given and unavoidable and thought, one has to postulate the existence of an omnipresent "aether or ether" to accommodate Maxwell's equations to the principle of inertia, according to which the physics is invariant under changes from one inertial reference frame to another in terms of the Galileo transformation of Newton-Galilean mechanics. Their way out was to postulate that there is this substance named ether defining an absolute inertial reference frame as its rest frame, which would imply that you could measure the absolute velocity of a body relative to this absolute inertial restframe. Others had thought, the Maxwell equations would have to be modified such as to fulfill the principle of inertia in the Galilei-Newton sense, but it was quickly clear that this destroys the success of Maxwell's equations in describing all electromagnetic phenomena known at the time with great accuracy. Also the properties of the hypothetical ether became more and more obscure the longer the physicists tried to make sense of it.
So it came as a great surprise, how simply a quite unknown clerk at the Bern patent office could solve this outstanding problem in the foundations of physics! The idea was to take Maxwell's equations as correct as given and demand the validity of the principle of inertia at the same time. Maxwell's equations together with the principle of inertia, however immediately then imply that the phase velocity of electromagnetic waves are the same (in a vacuum), independent of the speed of their source. Now, this implies the existence of a universal speed in the vacuum, the speed of light. The important thing is that this speed of light is finite, i.e., it takes time to transmit a signal from one place to another (at least as long as you use light).
Now to define a (global) reference frame you must establish an origin for time and space and some periodic thing that provides the standard unit for time intervals. Nowadays this is provided by a certain hyperfine transition radiation of Cesium to define the second as the unit of time. Now you have defined how to measure time at one point in space we take as the origin of our reference frame. Now you also have to define a distance measurement, and that's pretty easy now: Since there is the universal speed of light, you just send out a spherical wave packet, whose wave front defines the distance c t from the origin.
Then, if you want to tell a distant observer, how much ticks your standard clock has made measured from the time-zero point to make him synchronize his clock with yours, you have to take into account that you can do this only by sending out a light signal and thus you have to correct for the finite time \Delta t=L/c this signal needs to reach him. In this way you can place synchronized clocks at any point in space, even very far from the origin.
Thinking than about how an observer from another frame of reference that is moving to the original one with a constant speed relative to this original frame, you come to the conclusion that the Galileo-transformation rules must be abandoned and the Lorentz-transformation rules must be applied.
Analyzing this situation brings you pretty easily to the conclusion that the transformation must involve both spatial coordinates and time, that the transformation must be linear and such that it leaves the "Minkowski form" invariant, i.e., if (t,\vec{x}) are the time and space coordinates in the original inertial frame and (t',\vec{x}') are those in the new one, you must have
c^2 t'^2 -\vec{x}'^2=c^2 t^2 - \vec{x}^2,
where I have assumed that the origin of space and time of both reference frames are identical (for simplicity). That the transformation must be linear becomes clear from thinking about what the principle of inertia tells you: If a free mass point runs a straight line in one inertial frame this should be the case in any other inertial frame, no matter how fast they move against each other and in which direction. So you must map linear motion of a mass point with constant velocity in one inertial frame to a linear motion of this same mass point with (another) constant velocity in the other inertial frame. Thus the transformation must be linear.
Now it is pretty easy to derive the Lorentz transformation for the motion of the new frame with velocity v in x direction in the old frame:
c t'=\frac{c t-\beta x}{\sqrt{1-\beta^2}}, \quad x'=\frac{-\beta c t + x}{\sqrt{1-\beta^2}}, \quad y'=y, \quad z'=z.
Here, I've used the usual abbreviation \beta=v/c.
One remarkable conclusion is that this only makes sense if |\beta|<1! This means the speed of the new frame as measured in the old frame must be always smaller than the speed of light. As long as you obey this "absolute speed limit", there is no big obstacle in the conclusions to be drawn from this updated transformation law (i.e., using the Lorentz transformation instead of the Galileo transformation to change from one inertial frame to another).
Take, e.g., the famous phenomenon of "length contraction". Suppose you have a rod of length L along the x axis of the original inertial frame of reference and at rest relative to this frame. Then the one end of the rod is at the origin x_1=0 and the other point then necessarily at x_2=L. Now, how do you measure the length of the rod in the new inertial frame? You look at the same time t'=0 on the coordinates of the two end points in the new frame!
Now the first point is at t=t'=0 at x=x'=0. However, now the new length is read off by looking at the x' coordinate of the second end point at t'=0. In order for that to be compatible with the Lorentz transformation, the read-off of the x' coordinate, which is L', i.e., the length of the rod in the new frame must have been at a time t_2 \neq 0 as seen from the old coordinate frame since we must have
c t_2'=0=\frac{c t_2-\beta L}{\sqrt{1-\beta^2}} \; \Rightarrow \; c t_2=\beta L.
Then the Lorentz transformation tells us that the x' coordinate of this end of the rod in the new frame must be
L=\frac{-\beta c t_2+L}{\sqrt{1-\beta^2}}=\frac{L(1-\beta^2)}{\sqrt{1-\beta^2}}=L \sqrt{1-\beta^2}.
This shows that the rod, in the reference frame, where it is moving appears to be shorter due to the necessity to read off the coordinates of the ends of the rod at the same time in the new frame.
As soon as you have the Lorentz transformation derived, there's no much trouble anymore to get all these kinematical effects (length contraction, time dilation, relativity of simultaneity, twin paradox...) which seem so unusual to us, we are dealing with speeds very small relative to the speed of light, since then the finite signal time doesn't play a role, but it's only unusual due to this everyday experience, it's not unusual or strange given the fact that there is a universal speed limit at place and that we have to synchronize our clocks taking this speed limit into account.
