This first answers the question as originally posed and then the amended question. In both parts, I'll be using $\max(|a+b|,|a-b|)=|a|+|b|$.
The original inequality does not hold without constraints. A counterexample is given by $x_1=y_2=1$, $x_2=y_1=0$, $t=\pi/2$.
To find this, note that the left-hand side is extremal if the cosine is $\pm1$. Thus we would want to show that
$$\max\left(|x_1-y_1+x_2-y_2|,|(x_1-x_2)\pm(y_1-y_2)|\right)\ge ||x_1|-|y_1||+||x_2|-|y_2||$$
for both of the signs. For the minus sign, corresponding to $t=0$, this is indeed the case:
$$
\begin{eqnarray}
&&\max\left(|x_1-y_1+x_2-y_2|,|(x_1-x_2)-(y_1-y_2)|\right)
\\
&=&\max\left(|(x_1-y_1)+(x_2-y_2)|,|(x_1-y_1)-(x_2-y_2)|\right)
\\
&=&|x_1-y_1|+|x_2-y_2|
\\
&\ge&||x_1|-|y_1||+||x_2|-|y_2||\;.
\end{eqnarray}
$$
However, for the plus sign, we'd have to show that
$$\begin{eqnarray}
&&\max\left(|x_1-y_1+x_2-y_2|,|x_1-x_2+y_1-y_2|\right)
\\
&=&\max\left(|x_1-y_2+x_2-y_1|,|x_1-y_2+y_1-x_2|\right)
\\
&\ge&||x_1|-|y_1||+||x_2|-|y_2||\;,
\end{eqnarray}
$$
which isn't the case because the variables are now paired up the wrong way and the left-hand side can be made zero independently of the right-hand side.
Now assume $|x_1|\ge|x_2|$ and $|y_1|\ge|y_2|$, and consider the stronger inequality
$$\max\left(\big|x_{1}-y_{1}+x_{2}-y_{2}\big|,\big|\left|x_{1}-x_{2}\right|-\left|y_{1}-y_{2}\right|\big|\right)\ge\big|\left|x_{1}\right|-\left|y_{1}\right|\big|+\big|\left|x_{2}\right|-\left|y_{2}\right|\big|\;,$$
which would imply the original inequality, since $|x_1-x_2+y_1-y_2|\ge\big|\left|x_{1}-x_{2}\right|-\left|y_{1}-y_{2}\right|\big|$.
Consider first the case where $x_2-x_1$ and $y_2-y_1$ have the same sign. Then we have
$$
\begin{eqnarray}
&&
\max\left(\big|x_{1}-y_{1}+x_{2}-y_{2}\big|,\big|\left|x_{1}-x_{2}\right|-\left|y_{1}-y_{2}\right|\big|\right)
\\
&=&
\max\left(\big|x_{1}-y_{1}+x_{2}-y_{2}\big|,\big|x_{1}-x_{2}-y_{1}+y_{2}\big|\right)
\\
&=&
\max\left(\big|(x_{1}-y_{1})+(x_{2}-y_{2})\big|,\big|(x_{1}-y_{1})-(x_{2}-y_{2})\big|\right)
\\
&=&
|x_{1}-y_{1}|+|x_{2}-y_{2}|
\\
&\ge&
\big|\left|x_{1}\right|-\left|y_{1}\right|\big|+\big|\left|x_{2}\right|-\left|y_{2}\right|\big|\;.
\end{eqnarray}
$$
On the other hand, if $x_2-x_1$ and $y_2-y_1$ have opposite signs, we have
$$
\begin{eqnarray}
&&
\max\left(\big|x_{1}-y_{1}+x_{2}-y_{2}\big|,\big|\left|x_{1}-x_{2}\right|-\left|y_{1}-y_{2}\right|\big|\right)
\\
&=&
\max\left(\big|x_{1}-y_{1}+x_{2}-y_{2}\big|,\big|x_{1}-x_{2}+y_{1}-y_{2}\big|\right)
\\
&=&
\max\left(\big|(x_{1}-y_{2})+(x_{2}-y_{1})\big|,\big|(x_{1}-y_{2})-(x_{2}-y_{1})\big|\right)
\\
&=&
|x_{1}-y_{2}|+|x_{2}-y_{1}|\;.
\end{eqnarray}
$$
Since the constraints and the expression $\big|\left|x_{1}\right|-\left|y_{1}\right|\big|+\big|\left|x_{2}\right|-\left|y_{2}\right|\big|$ that this is to be compared with contain only the absolute values of the variables, we can assume without loss of generality that all variables are positive, as this will minimize the value out of all combinations of signs. Then the constraints become $x_1\ge x_2$ and $y_1\ge y_2$. Further, since the problem is symmetric with respect to interchange of the $x$s and $y$s, we may assume without loss of generality that $x_1\ge y_1$. That leaves only the relation of $x_2$ to $y_1$ and $y_2$ undecided. If $x_2\ge y_1\ge y_2$, then
$$|x_1-y_2|+|x_2-y_1|=x_1-y_1+x_2-y_2=\big|\left|x_{1}\right|-\left|y_{1}\right|\big|+\big|\left|x_{2}\right|-\left|y_{2}\right|\big|\;.
$$
If instead $y_1\ge x_2\ge y_2$, that only flips a sign on the left-hand side, in favour of the inequality. If instead $y_1\ge y_2\ge x_2$, that flips the sign on both terms containing $x_2$; the sign changes for $x_2$ cancel, and since $y_1\ge y_2$, the sign changes on $y_1$ and $y_2$ work in favour of the inequality. Thus the inequality is satisfied in all cases.
