The special theory of relativity is really enough to see that gravitational signals have to propagate by the speed $c$ which we call "speed of light" because the light is the most commonly understood entity that is moving by this maximum speed. Special relativity is OK to describe infinitesimal deformations of spacetime.
All other massless particles also have to propagate by the same speed $c$ because this speed $c$ is needed to enhance the vanishing rest mass to a finite total relativistic energy. And gravitons are inevitably massless because they don't pick any preferred reference frame - or, alternatively, because gravity is a long-range force. Massive particles could only induce short-range forces (similar to the weak nuclear force caused by W,Z bosons).
Any particle - e.g. neutrino - whose energy is much greater than the rest mass is moving nearly by the speed of light, too. The same thing would hold for massless scalar particles such as the "moduli" (their quanta) if they existed. It's an elementary consequence of the formulae of special relativity. The speed of light is the maximum speed that the information and material objects may pick, by causality, and it's also the typical speed that massless (exactly) and light (approximately) particles actually choose.
So the answer to your last question is No, the appearance of the same speed $c$ doesn't imply any additional dynamical relationship between electromagnetism and gravity - it's a direct and elementary consequence of the special theory of relativity - and its kinematics - that was fully understood in 1905. The importance of the speed $c$ in the scheme of things - because of special relativity - is so high that adult physicists use units in which $c=1$ and they are never ever surprised when $c$ plays an important role - it's exactly the same degree of "surprise" as if the number $1$ appears somewhere in maths.