We toss each of $n$ symmetrical coins repeatedly until we get the first heads. Let $X_i$ be the number of tosses needed to get the first heads with the $i$-th coin. Let $X$ be a median of $X_1,...,X_n$, i.e. the $\lfloor \frac{n}{2} \rfloor$-th smallest value in $X_1, ..., X_n$.
What is the best upper bound of $P(X \ge A)$ using Markov's/Chebyshev's/Chernoff's inequality? What is the order of magnitude of $EX$?
Let us fix $A \geq 1$, and first consider the probability that a single fair coin takes at least $A$ tosses before being heads. This is described by a geometrical distributed, with success probability $p = 1/2$ so that
$$\mathbf{P}(X_i = k) = 2^{-k},$$
from which we have
\begin{align*} \mathbf{P}(X_i \geq A) & = 1 - \mathbf{P}(X_i \leq A -1 )\\ & =1 - \sum_{k=1}^{A-1}2^{-k} \\ & = 2^{-(A-1)}. \end{align*}
Now consider the variable $Y_i = \mathbf{1}(X_i \geq A)$ which is $1$ if it takes at least $A$ tosses to achieve a head, and is $0$ otherwise. Then $Y_i$ is binomially distribution with
$$\mathbf{P}(Y_i = 1) \, = \, \mathbf{P}(X_i \geq A) \,=\, 2^{-(A-1)}.$$
Further we can define $Y = \sum_{i=1}^n$ to be the total number of coins that take at least $A$ flips before showing a head; since each coin is assumed to be independent and identically distributed, $Y$ has a Bernoulli distribution $\text{Ber}(n, 2^{-(A-1)})$.
The probability that you are interested in is therefore the probability that the above Binomial distribution exceeds $n/2$.
To compute this exactly we would require a closed expression for the CDF of a binomial distribution, which does not exist. According to wikipedia, for a general Binomial distribution $Z = \text{Bin}(n,p)$ so long as $p < k/n < 1$
$$ \mathbf{P}(Z \geq k) \leq \exp \left( - n \,D \left(\frac{k}{n} \bigg|\bigg|\, p \right) \right) $$ where $D$ is given by
$$ D(a \, | | \, b) = a \log \frac{a}{b} + (1- a) \log \frac{1-a}{1-b},$$ which is the relative entropy between two Bernoulli distributions.
In your context, we have that $p = 2^{-(A-1)}$, whilst $k = [n/2]$. So for $A \geq 3$the requirement on $p,k,n$ is satisfied; we will make the simplification of setting $k = n/2$ to simplify the algebra; then
\begin{align*} D\left( \frac12 \, \bigg|\bigg| \, 2^{-(A-1)} \right) & = \frac12 \log \frac 1{2^A} + \frac12 \log \frac{1}{2( 1- 2^{-(A-1)} )} \end{align*} and hence \begin{align*} \mathbf{P}\left(Y \geq \frac{n}{2}\right) & \leq 2^{-A \frac{n}2} 2^{-\frac{n}2} \left( \frac1{1 - 2^{1-A}} \right)^{\frac{n}2} \\ & = \left( \frac{2^{-(A+1)}}{1 - 2^{1-A}} \right)^{\frac{n}2} \\ & = \frac14 \left( \frac{1}{2^{A-1} - 1} \right). \end{align*}