It is clear that $\frac{1}{2} \geq \frac{(-1)^n}{n}, \forall n \in \mathbb{N} \implies \frac{1}{2}$ is an upper bound of $A$.
My intention is to make use of the lemma,
Assume $s \in \mathbb{R}$ is an upper bound for a set $A \subset \mathbb{R}$. Then, $s = sup(A)$ iff, $\forall \epsilon > 0$, $\exists a \in A$ satisfying $s - \epsilon < a$.
Let $\epsilon > 0$ be arbitrary. There are two cases,
Case 1: $\epsilon = \frac{1}{2}$
Choose $n = 2$ (Note that this particular $n$ works $\frac{1}{2} > \frac{1}{2} - \frac{1}{2} = 0$)
Case 2: $\epsilon \neq \frac{1}{2}$
Choose some $n$ satisfying $n < \frac{1}{\sqrt{\epsilon^2 - \epsilon + \frac{1}{4}}} \implies \frac{1}{n^2} > \epsilon^2 - \epsilon + \frac{1}{4} \implies \frac{(-1)^n}{n} > \frac{1}{2} - \epsilon$
QED.
I mostly seek for a solution that makes use of that lemma, but I am willing to be open to any solutions that you come up with.
There is no need to separate the cases. No matter what $\epsilon$ you take, it is always true that you can choose $\frac12\in A$ (i.e., the element you get if you choose $n=2$).
Because $\frac12\in A$, it is clear that whatever $\epsilon>0$ you are given, you have
$$\frac12 > \frac12-\epsilon$$
and this is already enough.
In fact, this is a good starting point to prove a more general result:
You can prove this statement more or less exactly from your lemma.