Why does potential-based reward shaping seem to alter the optimal policy in this case?
The same $\gamma = 0.9$ that you use in the definition $F \doteq \gamma \Phi(s') - \Phi(s)$ should also be used as the discount factor in computing returns for multi-step trajectories. So, rather than simply adding up all the rewards for your different time-steps for the different trajectories, you should discount them by $\gamma$ for every time step that expires.

Therefore, the returns of the blue route are:

$$0 + (0.9 \times -1) + (0.9^2 \times 0) + (0.9^3 \times 1) = -0.9 + 0.729 = -0.171,$$

and the returns of the red route are:

$$(0 + 0.9 \times 100 - 0) + 0.9 \times (1 + 0.9 \times 0 - 100) = 90 - 89.1 = 0.9.$$