Let $\mathcal F$ be the set of functions $$f(\boldsymbol M) = \left\langle \boldsymbol M, \boldsymbol u\boldsymbol v^\intercal\right\rangle$$ for all $\left\|u\right\| = \left\|v\right\| =1$.
Given a sequence $\boldsymbol X$ of random matrices, $\varepsilon$ a sequence of Rademacher (i.e., symmetric Bernoulli) random variables and $f\in \mathcal F$, let
$$\mathbb Ef = \mathbb E\left[f\left(\boldsymbol{X}_i\right)\right] = f\left(\boldsymbol A\right),$$
$$\mathbb E_{n, \boldsymbol X}f = \frac1n \sum_{i=1}^n f\left(\boldsymbol X_i\right)$$
and
$$\mathbb E_{n, \varepsilon, \boldsymbol X}f = \frac1n \sum_{i=1}^{n}\epsilon_i f\left(\boldsymbol X_i\right)$$ and for a functional $\boldsymbol L$ on $\mathcal F$ $$\left\|\boldsymbol L\right\|_{\mathcal F} = \sup_{f\in \mathcal F} \left\|\boldsymbol Lf\right\|.$$
Finally, we denote by $\alpha$ the value pf $\sup_{f\in \mathcal F}\mathbb P\left[\left|\mathbb E_{n, \boldsymbol X}f - \mathbb Ef\right| \ge t\right]$ and $$B=\left\{\left\|\mathbb E_{n,\boldsymbol X} - \mathbb E\right\|_{\mathcal F}> 3t\right\}.$$
The inequality that you are looking for is equivalent to
$$\mathbb P\left[B\right] \le \alpha + 4\mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F}> t\right].$$
Let $\boldsymbol Y$ be a sequence of random matrices independant from $\boldsymbol X$ and has the same distribution as $\boldsymbol X$.
Since if $\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E\right\|_{\mathcal F} > 3t$ there will be $g\in \mathcal F$ such that $$\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t,$$
then $$\sup_{g\in\mathcal F}\mathbb P\left[\left.\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\,\Big|\right.\boldsymbol X\right] = \mathbf 1_{B}$$
\begin{align}
\mathbb P\left[\left.\left\{\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right\}\cap B\,\Big|\right.\boldsymbol X\right] &\ge\sup_{g\in\mathcal F}\mathbb P\left[\left.\left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb E_{n, \boldsymbol Y}g\right| > 2t\right\} \cap \left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\right\}\,\Big|\right.
\boldsymbol X\right]\\
&= \sup_{g\in\mathcal F}\mathbb P\left[\left.\left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| - \left|\mathbb E_{n, \boldsymbol Y}g - \mathbb Eg\right| > 2t\right\}\cap \left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\right\}\,\Big|\right.\boldsymbol X\right]\\
&= \sup_{g\in\mathcal F}\mathbb P\left[\left.\left\{\left|\mathbb E_{n, \boldsymbol Y}g - \mathbb Eg\right| < \left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| - 2t \right\}\cap \left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\right\}\,\Big|\right.\boldsymbol X\right]\\
&\ge \sup_{g\in\mathcal F}\mathbb P\left[\left.\left\{\left|\mathbb E_{n, \boldsymbol Y}g - \mathbb Eg\right| < t\right\}\cap \left\{\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\right\}\,\Big|\right.\boldsymbol X\right]\\
&= \sup_{g\in\mathcal F}\left(\mathbb P\left[\left|\mathbb E_{n, \boldsymbol Y}g - \mathbb Eg\right| < t\right]\mathbb P\left[\left.\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\,\Big|\right.\boldsymbol X\right]\right)\\
&\ge \left(\inf_{f\in\mathcal F} \mathbb P\left[\left|\mathbb E_{n, \boldsymbol Y}f - \mathbb Ef\right| < t\right]\right)\left(\sup_{g\in\mathcal F}\mathbb P\left[\left.\left|\mathbb E_{n, \boldsymbol X}g - \mathbb Eg\right| > 3t\,\Big|\right. \boldsymbol X\right]\right)\\
&= \left(1 - \sup_{f\in\mathcal F} \mathbb P\left[\left|\mathbb E_{n, \boldsymbol Y}f - \mathbb Ef\right| \ge t\right]\right)\mathbf 1_B\\
&= \left(1 - \alpha\right)\mathbf 1_B.
\end{align}
This proves that,
\begin{align}
\mathbb P\left[\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right]
&\ge \mathbb P\left[\left\{\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right\}\cap B\right]\\
&= \mathbb E\left[\mathbb P\left[\left.\left\{\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right\}\cap B\,\Big|\right.\boldsymbol X\right]\right]\\
&\ge \left(1-\alpha\right) \mathbb E\left[\mathbf 1_{B}\right]\\
&= \left(1-\alpha\right) \mathbb P\left[B\right]
\end{align}
On the other hand,
\begin{align}
\mathbb P\left[\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right] &= \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X} - \mathbb E_{n, \varepsilon, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right]\\
&\le \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F} + \left\|\mathbb E_{n, \varepsilon, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right]\\
&\le \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F} > t\right] + \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol Y}\right\|_{\mathcal F} > t\right]\\
&= 2 \mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F} > t\right]
\end{align}
Finally,
\begin{align}
\mathbb P\left[B\right] &= \alpha \mathbb P\left[B\right] + (1-\alpha)\mathbb P\left[B\right]\\
&\le \alpha + (1-\alpha)\mathbb P\left[B\right]\\
&\le \alpha + \mathbb P\left[\left\|\mathbb E_{n, \boldsymbol X} - \mathbb E_{n, \boldsymbol Y}\right\|_{\mathcal F} > 2t\right]\\
&\le \alpha + 2\mathbb P\left[\left\|\mathbb E_{n, \varepsilon, \boldsymbol X}\right\|_{\mathcal F} > t\right].
\end{align}
and that finishes the proof.