How does one find a non-quadratic residue modulo $p$?
You are completely right, and your algorithm is a randomized polynomial time algorithm for finding a quadratic non-residue modulo a prime. A major open question in algorithmic number theory is finding a quadratic non-residue deterministically in polynomial time. This is possible assuming the generalized Riemann hypothesis, but unknown unconditionally. It is also equivalent to extracting square roots modulo a prime. This is all explained in notes by Booher.