It's not entirely coincidence.

Four dimensional space-time has a metric analogous to but not quite the same as euclidean space: the time part has the opposite sign from the space parts.

  ds^2 = (c dt)^2 - (dx^2 + dy^2 + dz^2)

ds is an "invariant proper time" which has the same value in all frames of reference. Check any special relativity textbook for the details.

Just as you can start with distance and then build up to momentum and energy in classical physics, in relativistic mechanics you can start with this metric and build up vectors in 4-space for velocity and energy/momentum. (Turns out that the time part is an energy while the space parts are momentum.) The upshot is that

  (m_0 c^2)^2 = E^2 - (p c)^2

which is the frame-invariant length of the energy-momentum 4-vector. (I think that m is better written as m_0, the rest mass, since the "m" notation sometimes means relativistic mass, which is different.)

No, it is not a coincidence [0]. It is a direct result of the fact that in relativity temporal and spatial information has to be unified into a single vector (a four-vector [1]). Since (in the Noether theorem sense [2]) energy is the conserved quantity related to symmetry of displacements in time and momentum is the conserved quantity related to symmetry under displacements in space, it is quite natural to unite them into one four vector, related to symmetry of displacements in spacetime.

What's peculiar is that the temporal entry of the four vector gets the "opposite sign" for the Pythagorean theorem. That is, if you have a vector (t, x, y, z), then the "hypotenuse" (called an invariant) is t^2 - x^2 - y^2 - z^2 (up to a conventional choice of overall sign). What's surprising is that the hypotenuse is the thing that's the same for different observers. So, if you do a Lorentz transformation [3], t and the spatial entries will change, but the invariant combination won't.

Everybody knows E = mc^2 is the relationship between a particle's mass and its energy. But what is its energy if it's moving? Certainly the particle gains energy the faster it moves, right? Yes. E = mc^2 is the 0-momentum version of a relativistic expression. Since E is temporal and momentum p is spatial, the four vector can be written (E, pc), which has an invariant E^2 - (pc)^2. We call this invariant the rest mass[4], up to some factors of c. Algebraically moving things around gives us the "Pythagorean" form.

[0] https://en.wikipedia.org/wiki/Energy%E2%80%93momentum_relati...

[1] https://en.wikipedia.org/wiki/Four-vector

[2] https://en.wikipedia.org/wiki/Noether%27s_theorem

[3] https://en.wikipedia.org/wiki/Lorentz_transformation

[4] https://en.wikipedia.org/wiki/Invariant_mass

Yes (but also no). The initial form of this equation is

    (mc^2)^2 = E^2 - (pc^2)^2

The Pythagorean theorem tells you the length of a 2D vector when you know x and y lengths. Here mc^2 is the length of the 4-momentum vector [E, pc^2] (where p is a standard 3D vector). However since our 4D spacetime is not Euclidian but Minkowskian the sign in the generalised Pythagoras theorem is a minus and not a plus.