What does $\hat{\theta}_n = \theta + O_p(n^{-1/2})$ mean in terms of rates? For $\hat{\theta}_n = \theta + O_p(n^{-1/2})$ we have $$\hat{\theta}_n - \theta =  O_p(n^{-1/2})$$
Therefore, we have for any $\epsilon > 0$, there exists a finite $M > 0$ and finite $N > 0$ such that for all $n > N$,
$$P\left(|\sqrt{n}(\hat{\theta}_n-\theta)| > M\right) < \epsilon$$ The above means that $\sqrt{n} (\hat{\theta}_n -\theta)$ is bounded in probability.
However, what exactly does $\hat{\theta}_n - \theta = O_p(n^{-1/2})$ mean in words? Is it that "the difference between $\hat{\theta}_n$ and $\theta_n$ is diminishing at rate $n^{-1/2}$"?

It depends on what you are referring to with "the difference between $\hat \theta_n$ and $\theta_n$".
Intuitively, it means that the larger $n$ becomes, the less likely it is that the difference is not less than proportional to $n^{-1/2}$. But there could always be cases where this is not true, it's only that they get exceedingly unlikely.
