Although it may not be the intention of the OP, questions like the OP's question
(in my opinion) sometimes places the burden on Relativity to explain its peculiarities.
One way to respond to such questions is show that similar peculiarities occur elsewhere...although often not noticed. I think the following example is compatible with some of the early comments in this thread...
Inspired by the SR-formulation of spacetime, one can go back and consider the situation for the Galilean case (i.e. the ordinary position vs. time graph in PHY 101). Depending on conventions and definitions, the analogous question is
"Why in the Galilean spacetime-interval [in my conventions... it gives the square of the elapsed proper time in a Galilean spacetime]
## ds^2=dt^2 -\left(\frac{c_{signal}}{c_{light}}\right)^2 dy^2 = dt^2 - 0 dy^2=dt^2.##
is there a "zero" instead of a "plus 1"?" (c_{signal}=\infty in the Galilean case.)
So, one answer is that the position-vs-time-graph (whether in SR or ordinary PHY 101)
does have not a Euclidean geometry [where the Pythagorean theorem holds]. For PHY 101 (as well as SR), this means that
two line-segments on a pos-vs-time graph (say one for an object at rest and one moving with a nonzero velocity) with the same Euclidean length do not correspond to the same elapsed time.
So this can be start of a line of reasoning in which it is realized that not every geometry that arises in physics is necessary Euclidean... e.g. spherical geometry, phase space, PV-diagrams, etc... One can then go on and try to give some physical or mathematical intuition [likely based on what concepts are viewed as fundamental] as to why it is so... as others here have done.
The answer I gave above based on the Galilean spacetime is an extension of Minkowski's 1907 formulation, which is based on the Cayley-Klein projective geometries.
To me, causality (in the sense that not all events can be totally-ordered by causal relations) is at the root of the answer. (Along these lines, one can start at AA Robb's 1914 formulation
http://archive.org/details/theoryoftimespac00robbrich... then somehow make the appropriate assumptions [e.g. continuity, homogeneity, etc...] to arrive at the Minkowski metric (for example.. something like
http://www.mcps.umn.edu/assets/pdf/8.7_Winnie.pdf ). From this point of view, it is research problem to start with causality at a microscopic level to recover [i.e. explain] the geometrical structures of continuum general relativity.