EM and GR don't actually say that "particles exert forces on each other". What they actually say is that particles produce electromagnetic and gravitational fields, and that these fields then interact with other particles. Significantly these theories describe these fields using differential equations, which means that the field at some point in space is completely defined by the field in its immediate neighbourhood. If a charged or massive particle accelerates, this causes a change in the local field around the particle, which creates a disturbance that propagates outwards as the field reconfigures itself. This disturbance propagates at the speed of light (in fact in the EM case it is light) so there is no violation of locality.
It is important to realise that the principle of locality requires that these fields are in some sense "physically real" (whatever that means) and are more than just a clever bit of maths. In the case of GR we have a nice picture of the field in terms of the bending of space time, while trying to understand what an EM field is leads to QFT.