Why does a negative reward for every step really encourage the agent to reach the goal as quickly as possible?
Your examples are equivalent. But it is possible to find a constant yielding  a different optimal policy.
Your examples are absolutely equivalent. The agent maximizes the reward, and only way to do so is by reaching $s^*$.
Consider $r_3$ :
$$
r_3(s, a)=
\begin{cases}
1, &amp; \text{ if }  s \neq s^*\\
2, &amp; \text{ otherwise}
\end{cases}
$$
With a sufficiently large $\gamma$, moving infinitely without reaching $s^*$ is now the optimal solution.
For the generic case
$$
r_4(s, a)=
\begin{cases}
\alpha, &amp; \text{ if }  s \neq s^*\\
\beta, &amp; \text{ otherwise}
\end{cases}
$$
the threshold is found by comparing the results of the series $\alpha + \alpha^2 + \alpha^3 + ... + \alpha^{t_m}$, where $t_m$ is the maximum episode length, and $\alpha + \alpha^2 + \alpha^3 + ... + \alpha^{t^*}$, where $t^*$ is the length of the episode following the fastest policy.
In the example of $r_3$, it is trivial to find examples where the fastest policy isn't optimal. Imagine a race, the agent starts on the left and gets either $\alpha$ or $\beta$ points, depending on where it is. With $\gamma = 0.9$ and no time-limit (infinite episodes) the optimal policy is  to move randomly, but in the second-to-last house, avoid the goal state. With $\gamma = 0.1$, the optimal policy is to move randomly (not really, probably there would be a slight advantage in moving right), but in the second-to-last house, enter the goal.