In Faraday's experiment, the relative velocity between the coil and the magnet define whether a change of induced magnetic field flux occurs around the coil or not. So if you consider them at rest, and when you consider them moving at the same velocity relative to one another, then there's no change of magnetic field flux felt by the coil.
Be careful there are only two interpretations of the Faraday's experiment, in the first one, one studies the change of flux in the coil, so the observer is in the coil's frame of reference, and in the second interpretation (which does not always hold) the observer is sitting on the magnet, and the current in the coil caused by the Lorentz force is studied.
Elaboration of the first interpretation: Observer in coil's frame of reference:
![enter image description here][1]
Flux of the induced magnetic field $\vec{B}$ : $$\Phi = \int \int_{S} \vec{B} d\vec{S} $$
Where "S" is the surface confined by the coil. Due to the relative motion of coil-magnet, the total flux increases and induces a difference of potential: $$ V = -\frac{d\Phi}{dt} $$
Finally as for your relativity argument, it hold perfectly here in the sense that the physics in either frames is the same, as the driving element in Faraday's law is defined by the relative motion of the coil-magnet pair, whereas for an outside observer, although a change of magnetic flux is created around the observer due to the motion of the magnet, but as the coil (in your example) is moving with the same velocity, the change of $\Phi$ is not felt by the coil. [1]: https://i.sstatic.net/P7RkC.png
