General question on approach to showing sample size required is $\Omega(\cdot)$
There is a difference between the two questions. Let $p_n$ be the number of heads in $n$ trials divided by $n$. We know that for large $n$, $p_n$ is very close to $p$; qualitatively this is the law of large numbers, and quantitatively this is the central limit theorem. This phenomenon is known as concentration. This is what you use to give an upper bound on $n$. In contrast, to give a lower bound on $n$ you need to show anti-concentration: that for small $n$, $p_n$ has a reasonable probability of being somewhat far from $p$. The techniques for showing anti-concentration are often more delicate.

In your particular example, concentration can be shown using classical inequalities such as Chernoff's inequality. For anti-concentration you can use the Paley–Zygmund inequality, but you won't necessarily get good bounds. To get nearly tight bounds you can use a general-purpose double-sided inequality such as Berry–Esseen, or a specialized one à la de Moivre–Laplace.