Mathematically, you define distance in SR as the invariant interval (geodesic length) between a pair of simultaneous events. In relativity, simultaneity differs between observers in relative motion. As a result, their notions of distance also differ.
More physically, you can define distance using some reasonable procedure, e.g. parallax, image size, radar ranging. However, the first two relate a nearby size or distance with a distant size or big distance. Thus they need a definition of distance to get started. You can use radar ranging (or light travel time) to get started, or as your main definition. Going with radar for simplicity (in SR it is provable that they are all the same, for inertial observers), consider what Anthony and Cleopatra do. If each measures distance to some third object (in some state of motion), the round trip light paths will be radically different because of the relative motion between Anthony and Cleopatra. Thus, they measure the universe completely differently.