  Given $N_{\textrm{tot}}$ applications of a unitary operation with an unknown
phase $\theta$, a large-scale fault-tolerant quantum system can {reduce} an
estimate's {error} scaling from $\mathcal{O} \left[ 1 / \sqrt{N_{\textrm{tot}}}
\right]$ to $\mathcal{O} \left[ 1 / {N_{\textrm{tot}}} \right]$. Owing to the
limited resources available to near-term quantum devices, entanglement-free
protocols have been developed, which achieve a $\mathcal{O} \left[
\log(N_{\textrm{tot}}) / N_{\textrm{tot}} \right]$ {mean-absolute-error}
scaling. Here, we propose a new two-step protocol for near-term phase
estimation, with an improved {error} scaling. Our protocol's first step
produces several low-{standard-deviation} estimates of $\theta $, within
$\theta$'s parameter range. The second step iteratively hones in on one of
these estimates. Our protocol's {mean absolute error} scales as $\mathcal{O}
\left[ \sqrt{\log (\log N_{\textrm{tot}})} / N_{\textrm{tot}} \right]$.
Furthermore, we demonstrate a reduction in the constant scaling factor and the
required circuit depths: our protocol can outperform the asymptotically optimal
quantum-phase estimation algorithm for realistic values of $N_{\textrm{tot}}$.
