The best constants comparing operator and Frobenius norms

Idea. Both norms are functions of the singular values: $\sigma_1$ against $\big(\sum\sigma_i^2\big)^{1/2}$. The ratio $\sigma_1/\big(\sum\sigma_i^2\big)^{1/2}$ is largest when only one singular value is non-zero, and smallest when all are equal.

Step 1: the upper constant. Since $\sigma_1^2\le\sum_i\sigma_i^2$, we have $\|A\|\le\|A\|_F$. Equality holds for the rank-one matrix $E_{11}$ (where $\|E_{11}\|=\|E_{11}\|_F=1$). So the smallest possible $C$ is $C=1$.

Step 2: the lower constant. Since $\sum_i\sigma_i^2\le n\sigma_1^2$, we have $\|A\|_F\le\sqrt n\|A\|$, i.e. $\frac1{\sqrt n}\|A\|_F\le\|A\|$. Equality holds for $A=I$, where $\|I\|=1$ and $\|I\|_F=\sqrt n$. So the largest possible $c$ is $c=\frac1{\sqrt n}$.

Conclusion.
$$\frac1{\sqrt n}\|A\|_F\le\|A\|\le\|A\|_F.$$

Remark. The constants are sharp for every $n$, but each of them is attained only on a very small set: the right one at rank-one matrices, the left one at multiples of orthogonal matrices (all singular values equal). For a "typical" random matrix the ratio $\|A\|_F/\|A\|$ is of order $\sqrt n/2$, closer to the lower extreme. As $n\to\infty$ these constants degenerate, which is why quantitative estimates in high dimension must keep track of the dimension.