Let $$a_n:=\dfrac23(4^n + 2).$$
Note that $\sum_{k=1}^{n-1}4^k=4^n-a_n$ and hence $P(|S_{n-1}|\le4^n-a_n)=1$. So, the equality $X_n=S_n-S_{n-1}$ and the triangle inequality imply 
$$P(|S_n|\ge a_n)\ge P(|X_n|=4^n,|S_{n-1}|\le4^n-a_n)=1$$
and hence 
$$P(|S_n|\ge a_n)=1.$$
On the other hand,
$$P(|S_n|=a_n)\ge P(X_n=4^n,S_{n-1}=-(4^n-a_n)) \\
=P(X_n=4^n,X_{n-1}=-4^{n-1},\dots,X_1=-4^1)=2^{-n}>0$$
and hence for all $r>a_n$ we have 
$$P(|S_n|\ge r)\le P(|S_n|>a_n)\le1-2^{-n}<1.$$
So, 
$$A_n=a_n.\quad\Box$$