Just as there is a difference in perceived time there's also a difference in perceived distance. As it turns out these cancel out in a way that ensures the speed of light is the same for all observers. Together with the axiom that everyone agrees whether something travels in a straight line you can figure out most of special relativity.

It's somewhat hard to explain why this works without handwaving or just pointing to the maths, but the youtube channel minute physics at least has some good visualizations: https://www.youtube.com/watch?v=Rh0pYtQG5wI