Suppose that $A$ and $B$ are two arbitrary $m\times n$ matrices with $m>n$. Let $\mathsf{U}_n$ denote the set of $n\times n$ unitary matrices. I'd like find positive constants $c_1$ and $c_2$ such that $$ \begin{align*} c_2\left\Vert AA^*-BB^*\right\Vert &\geq\inf_{R\in \mathsf{U}_n} \left\Vert A - BR\right\Vert^2_F \geq c_1\left\Vert AA^*-BB^*\right\Vert, \end{align*} $$ holds (and the inequalities are sharp enough). I'm more interested in the upped bound.
I have a partial answer that addresses some special cases. For example, if $n=1$ then I've shown that $c_2=\sqrt{2}$. Furthermore, if we assume that $A$ and $B$ have the same range, it's not difficult to find the appropriate $c_2$.
My conjecture is that $c_2 = \sqrt{2n}$, but I haven't been able to prove it. The infimum above is the standard orthogonal Procrustes problem and it is relatively straightforward to show that $$ \begin{align*} \inf_{R\in \mathsf{U}_n} \left\Vert A - BR\right\Vert^2_F &=\left\Vert A\right\Vert_F ^2 +\left\Vert B\right\Vert_F ^2 -2\left\Vert A^*B\right\Vert_*, \end{align*} $$ where $\left\Vert \cdot\right\Vert_*$ denotes the nuclear norm (or the Schatten 1-norm).