I think to answer this question concerning gravitation one should argue not with the final result that gravitational interaction (and inertia) can be reinterpreted as spacetime geometry a la general relativity, though this is of course a correct an important interpretation but conceptually the question is answered by the introduction of the field concept.
Interestingly already Newton had his quibbles with his action-at-a-distance law for gravity, which however is the only way to make the interaction between distant bodies compatible with the third law (actio=reactio). Already Newton was a bit quibbled by this action at a distance but since it worked so well with the celestial mechanics he just abandoned his quibbles by his famous statement "hypotheses non fingo" ("I don't make hypotheses").
The resolution of this quibble was the idea of the field concept, which is due to Faraday in connection with the electromagnetic interaction. Though he couldn't formulate this most important fundamental concept since Newton's mechanics in a mathematical way, he had a very good intuition. Then of course Maxwell with his mathematical realization of Faraday's field idea got it right as a relativistic local field theory though of course he had no idea about relativity.
The important feature of the field-theoretical view in connection with your question of consistency with relativistic causality (i.e., with the existence of a limiting speed of causal signal propagation) is that it is a local theory, i.e., the action of the electromagnetic force on a charged point particle is due to the presence of the electromagnetic field at the location of this point charge, and the electromagnetic field is taking part in the dynamics of a closed system as does the charged particles, i.e., the field is a fundamental dynamical degree of freedom, and Maxwell's equations tell how the field is created due to the presence of charges and currents and Lorentz's force tells the charges how to move (though this is a bit too optimistic a view concerning point particles, because there are serious problems with classical point particles in any relativistic field theory, and the solution of this is to describe the matter in terms of (relativistic) continuum mechanics in the classical realm or in terms of a relativistic QFT when quantum effects become important), and thus through the "mediation of the forces" through a dynamical field everything is consistent with the "fundamental speed limit".
Now the gravitational interaction is different from all other interactions in the sense that the socalled equivalence principle holds. This means that for a sufficiently small region in space, where the gravitational field acting on a point particle (caused by other matter creating this field) can be considered as homogeneous you can always find a reference frame where there is no gravitational force (you can realize it by a sufficiently small box in free fall, like the International Space Station, where you have only very little gravity inside, because it's freely falling). This is the socalled "weak equivalence principle". You can now also impose the "strong equivalence principle", i.e., you extend the possibility to find, in a sufficiently small region (more precisely spacetime region) always a frame of reference, where all the physical laws hold as if there's no gravitational field. If you think this to the end you end up with the conclusion that Lorentz invariance, which is a global symmetry in special relativity must be made a local symmetry. This opens all the mathematical machinery to make all kinds of models for matter and in addition you get a (pseudo-)metric and what's called a connection on a differentiable manifold. Further it turns out that in the macrocopic realm, where you can describe matter in terms of continuum mechanics and with electromagnetism as the only relevant interaction besides gravity, that the connection is torsion free and thus you end up with Einstein's general relativity, which is completely equivalent to say that gravity can be reinterpreted as a curved spacetime geometry, and also it turns out that everything is compatible with the "relativistic speed limit", i.e., what appears as a gravitational force acting on a freely falling test body in Newtonian mechanics is within GR just a force-free motion in the curved spacetime, and again the trajectory of the body is completely determined by local laws, namely that the trajectory of the freely falling body must be a geodesic of spacetime. How the spacetime geometry looks like in detail is described by Einstein's field equations, which tell "spacetime how to curve" (Wheeler), and thus the spacetime structure (described by the pseudometric of the Lorentz space) becomes a dynamical entity, and causal changes propagate with the same limiting as in special relativity which, to the best of our knowledge, is just the speed of light, because the electromagnetic field is with high accuracy massless. Quantitatively the upper bound of the related photon mass is ##m_{\gamma}<10^{-18} \text{eV}##.
