Finding a basis for quantum measurement with maximum distinguishability
I figured out what I missed. $\Delta Fidelity=\frac{1}{2}\left(r_x-r_z\right)$ is indeed correct. However, what I missed was the fact that $r_z$ could be less than 0, since the only requirement is that $\left|\vec{r}\right|\le1$. Therefore, to achieve the maximum value of $\Delta Fidelity$, we set $r_x=\frac{1}{\sqrt{2}}$ and $r_z=-\frac{1}{\sqrt{2}}$. This means the actual correct answer is $|\psi\rangle=\frac{|+\rangle+|1\rangle}{2cos\left(\frac{\pi}{8}\right)}$, because a density matrix with $r_z=-1$ and $r_x=r_y=0$ is the density matrix of the $|1\rangle$ state, and the state $|\psi\rangle$ is a midway state between $|+\rangle$ and $|1\rangle$.

Thus, the general approach I took was correct, but I initially failed at performing mathematical optimization in my head.