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}$"?

I like to view this intuitively in terms of quantiles. Then the notation for 'probability distributions' becomes exactly the same as 'regular' Landau-notation.
The expression $P\left(|\sqrt{n}(\hat{\theta}_n-\theta)| > M\right) < \epsilon$ means also that the $\epsilon$-th quantile $Q_{\epsilon}(  \vert\hat{\theta}_n-\theta\vert)$ of the distribution of $\vert \hat{\theta}_n-\theta   \vert $ is smaller than or equal to $M \cdot  \frac{1}{\sqrt{n}}$ at least for some sufficiently large $n>N$. And this is true for every quantile $\epsilon$.
The difference with small $o$ notation is that small-$o$ is independent of $M$. For every $M$ there will be some large enough $n>N$ such that the quantile is smaller.
With $O(f(n))$ we get that $\lim_{n \to \infty} \frac{Q_{\epsilon}(  \vert\hat{\theta}_n-\theta\vert)}{f(n)} \leq M$.  With $o(f(n))$ we get that $\lim_{n \to \infty} \frac{Q_{\epsilon}(  \vert\hat{\theta}_n-\theta\vert)}{f(n)} = 0$.
