The central postulate of relativity is that the speed of light is constant in every frame of reference. In Newtonian physics, this is impossible; if light is traveling at $c$ in one frame of reference, then someone traveling at velocity $v$ in the opposite direction would see light traveling at $c+v$. This led Einstein to conclude that Newtonian physics had foundational assumptions that were incorrect, namely that temporal and spatial distances are constant in every frame of reference. In relativity, if Alice and Bob are moving relative to each other, Bob will measure that Alice's clocks as going more slowly, and her distances to be shortened.
Clearly, even in Newtonian physics, the two people will disagree as to what happens constitutes the "same place"; since Bob views Alice as moving, what she considers the same place, Bob considers to be different places. For instance, suppose Alice is on a train. If she gets up from her seat, walks around, then sits back down in her seat, then from her perspective, she ended up in the "same" place. But to Bob, the whole train moved while Alice was walking around, so she did not end up in the same place. Relativity says that not only will they disagree about what is the "same place", but also what is the "same time".
So suppose Alice is on Earth, traveling at rest with respect to Earth, and Bob is out in space at rest with respect to the Cosmic Microwave Background. Alice observes three events: E1 is light be emitted in all direction, E2 is a photon being absorbed after traveling the same direction Earth is traveling, and E3 is a photon being absorbed after traveling in the direction opposite to Earth's direction. Alice observes E2 and E3 as being the same distance and same elapsed time relative to E2. Bob measures E3 to be less elapsed time, but he also measures E3 to be less distance, so he still measures the photon to be traveling at $c$.