I can do a somewhat worse estimate of $e^{ - n t^2/4}$. If I calculated right, the estimate you state is approximately true for $t$ small but fails for $t$ large, but if I got things the wrong way around then almost the same argument will give that estimate.

If the probability that $X_j \geq t$ is $p$, then the probability that at least $n/2$ of the $X_k \geq t$ is $$\sum_{j=n/2}^n \binom{n}{j} p^j (1-p)^{1-j} \leq \sum_{j=n/2}^n \binom{n}{j} p^{n/2} (1-p)^{n/2} \leq 2^n p^{n/2} (1-p)^{n/2} $$ as long as $p \leq 1/2$ (which it clearly is in this case).

To bound this by $e^{ - n t^2/4}$ we need the estimate $$2 \sqrt{\mathbb P (X_k \geq t) } \sqrt{ ( 1 - \mathbb P (X_k \geq t))} \leq e^{ - t^2/4}.$$

which is equivalent to $$\mathbb P (X_k\geq t) \leq \frac{1 - \sqrt{ 1 - e^{-t^2/2}}}{2}$$

or $$ ( 1- 2 \mathbb P ( X_k\leq t))^2 \geq 1 - e^{ - t^2/2}$$ which has the following geometric interpretation: We need the probability that two independent random samples of the Gaussian have absolute value at most $t$ to be at least $1- e^{ -t^2/2}$. This includes the case where the two independent random samples have sum of squares at most $t^2$, which since the sum of the squares of two Gaussians has an exponential distribution has probability exactly $1-e^{-t^2/2}$, as desired.

On the other hand the probability that two independent random samples of the Gaussian have absolute value at most $t$  $1- e^{- \frac{4}{\pi} t^2}$, since this is the probability that a point whose $x,y$ coordinates are sampled from the Gaussian lies in the box $[-t, t] \times [-t,t]$, which has the same area as the disc of radius $\sqrt{\frac{4}{\pi}}t$ centered on $0$. Replacing a box by a disc of the same area centered at zero rasises the probability and the same exponential argument gives $1- e^{- \frac{4}{\pi} t^2}$. So unless I got a sign wrong somewhere $1- e^{- \frac{4}{\pi} t^2}$ is a lower bound, not an upper bound, and doesn't help. (Though the lower bound is clearly asymptotically correct for $t$ small.)

I can do a somewhat worse estimate of $e^{ - n t^2/4}$. If I calculated right, the estimate you state is approximately true for $t$ small but fails for $t$ large, but if I got things the wrong way around then almost the same argument will give that estimate.

If the probability that $X_j \geq t$ is $p$, then the probability that at least $n/2$ of the $X_k \geq t$ is $$\sum_{j=n/2}^n \binom{n}{j} p^j (1-p)^{1-j} \leq \sum_{j=n/2}^n \binom{n}{j} p^{n/2} (1-p)^{n/2} \leq 2^n p^{n/2} (1-p)^{n/2} $$ as long as $p \leq 1/2$ (which it clearly is in this case).

To bound this by $e^{ - n t^2/4}$ we need the estimate $$2 \sqrt{\mathbb P (X_k \geq t) } \sqrt{ ( 1 - \mathbb P (X_k \geq t))} \leq e^{ - t^2/4}$$

which, squaring both sides and using $4x(1-x)=4x-4x^2 = 1-(1-2x)^2 $, is equivalent to $$1- ( 1- 2 \mathbb P ( X_k\leq t))^2 \leq e^{ - t^2/2}$$ which has the following geometric interpretation: We need the probability that one of two independent random samples of the Gaussian have absolute value at least $t$ to be at most $e^{ -t^2/2}$. This is at most the probability that the two independent random samples have sum of squares at least $t^2$, which since the sum of the squares of two Gaussians has an exponential distribution has probability exactly $e^{-t^2/2}$, as desired.

On the other hand the probability that two independent random samples of the Gaussian have absolute value at most $t$ is at most $1- e^{- \frac{4}{\pi} t^2}$, since this is the probability that a point whose $x,y$ coordinates are sampled from the Gaussian lies in the box $[-t, t] \times [-t,t]$, which has the same area as the disc of radius $\sqrt{\frac{4}{\pi}}t$ centered on $0$. Replacing a box by a disc of the same area centered at zero raises the probability and the same exponential argument gives $1- e^{- \frac{4}{\pi} t^2}$. So unless I got a sign wrong somewhere $e^{- \frac{4}{\pi} t^2}$ is a lower bound, not an upper bound, and doesn't help. (Though the lower bound is clearly asymptotically correct for $t$ small.)