Without Einstein, I think that the discovery of time dilation would be delayed by only a few years. There were a lot of people working in theoretical physics already back then; someone else would inevitably dig through Lorentz' and Poincaré's papers, connect the dots, and say "waitaminute time might be relative". From that, time dilation is a consequence.

In special I wouldn't doubt that Max Planck would discover it.

I'm saying that because, in both science and engineering, often you see almost concurrent discoveries or developments of the same thing, because the "spirit of a time" makes people look at that aspect of reality or that challenge and work with it. The discovery of helium and the development of aeroplanes are examples of that.

IIRC the orbit of Mercure doesn't work with Newton Model, and astronomers were predicted the discovery of Vulcain a small planet between Mercure and the Sun. So a new model had to be invented since Vulcain couldn't be found.

We would have definitely figured it out once we built GPS, since you need to account for relativistic effects there.