If Maxwell's equations relate fields at the same point, how can waves propagate between different points?

You are (roughly speaking) correct that “in order to achieve propagation an E˙ or B˙ in one place must be capable of inducing a B˙ or E˙ in a different place”. This can be seen directly in Maxwell’s equations.

Faradays law says $\nabla \times E = -\dot B$. Note that the curl is a spatial derivative, and the dot is a time derivative. So a B field changing in time gives an E field changing in space. This introduces coupled changes over time and space.

Similarly with Ampere’s law.

Looking at matter waves on a string: As long as the oscillations aren't too big, we get the wave equation for $f(x, t)$:

$$ \frac{\partial^2 f}{\partial t^2} = c^2\frac{\partial^2 f}{\partial x^2} $$

Your question applies to this equation just as well as it does to the equations of electricity and magnetism. Don't both the terms in this equation apply just to a single point? How can disturbances propagate through space without violating locality?

The key is to go back to the definition of a partial derivative:

$$ \frac{\partial f(x, t)}{\partial x} = \lim_{h \to 0} \frac{f(x+h, t) - f(x,t)}{h} $$

Now this next bit is going to get a little hand-wavey, since that's the nature of this question. This partial derivative doesn't just care about $f$ at the point $(x,t)$. It also cares about the value of $f$ in a tiny, ever-shrinking neighborhood right around $x$. Similarly, the derivative $\frac{\partial^2 f}{\partial x^2}$ cares about an arbitrarily small, but not point-like, neighborhood around $x$.

Suppose that we stop the shrinking of these neighborhoods at some point, so they have size $\epsilon$. Then instead of behaving like a string, our model behaves like a bunch of point masses connected by springs of length $\epsilon$. However, as $\epsilon$ goes to 0, this behavior approximates that of a truly continuous string.

So the short version of this answer is that having spatial derivatives in your PDE is what allows things happening in one point in space to affect other points in space. This has something to do with derivatives existing in a strange twilight zone where, on one hand they are local, but on the other they care about change over spatial distance.

And spatial derivatives appear in Maxwell's equations in the terms $\nabla\cdot E$, $\nabla\cdot B$, $\nabla\times E$, and $\nabla\times B$, so it shouldn't be too much of a mystery that light travels through space.

This answer is general, but too long for a comment.

When modeling physical behavior with mathematical functions one has to be clear:

Are we talking : a) mathematics creates reality or b)mathematics models reality.

a) is the platonic view and b) the realist view.

Under a) the predictive power of mathematics leads to questions as the ones above and they are answered by the other answers

Under b) one is not surprised by the underlying quantum mechanical level, that is modeled with a quantized maxwell equation, which eventually builds up the classical electrodynamics equations, as both depend on the same mathematics with different application. How the classical light description emerges from a confluence of probabilistic photons in quantum field theory is outlined here

Imo it is the realist view that physicists should have, using mathematics as a tool of modeling new data and asking questions of the theories that fit them. That is how science has progressed since the time of Newton.

A rough analogy for the classical electromagnetic wave:

If one maps a dry river bed mathematically, the shape of the water flow when it rains can be predicted immediately, long before the water reaches the bends. In a similar sense, Maxwell's equations map space time, and given the initial conditions (light beam) the "flow" is beautifully predictable.

edit after comments:

To carry my analogy to a map further, a map is static. That is because time is a parameter and does not enter in the functions describing a map, which can be very accurate and used to predict motion through it, it is the context for a flow.

Maxwell's equations are a four dimensional map. Static has no meaning in four dimensions , because time is one of the dimensions. Given the initial conditions , there is a complete solution. The predictive in time possibility is because one deals with time and space separately. but the solution for given boundary conditions,is unique in four dimensional spacetime.

The underlying quantum mechanical level of photons also explains why E and B can be zero at the same spacetime point, what happens to the energy ?

Electromagnetic waves can be imagined as a self-propagating transverse oscillating wave of electric and magnetic fields. This 3D animation shows a plane linearly polarized wave propagating from left to right. Note that the electric and magnetic fields in such a wave are in-phase with each other, reaching minima and maxima together.

The superposition of the zillions of photons making up the classical wave, also give a wavefunction for the whole bundle. The zeros mean that there is zero probability for a photon to exist at those points where both E and B are zero, thus energy conservation can be carried out at all space time points.