Effective bound on the expansion of the $j$-invariant

Once you know that the coefficients are all positive (see postscript), it's easy to get an effective upper bound that grows as $\exp(4\pi \sqrt{n})$, which is within a factor $O(\sqrt n)$ of the correct order of growth. Start from the inequality $$ a_n = q^{-n} (a_n q^n) < q^{-n} \sum_{k=-1}^\infty a_k q^k = q^{-n} j(\tau) $$ for any purely imaginary $\tau = it$ (because $q = e^{-2\pi t} > 0$ so each term $a_n q^n$ is positive). If $t \geq 1$ then $$ j(it) = e^{2\pi t} + \sum_{n=0}^\infty a_n e^{-2\pi n t} \leq e^{2\pi t} + \sum_{n=0}^\infty a_n e^{-2\pi n} = e^{2\pi t} + j(i) - e^{2\pi} < e^{2\pi t} + 1728. $$ Since $j(i/t) = j(it)$ it follows that also $$ j(it) < e^{2\pi/t} + 1728 $$ for $t \leq 1$. Thus our inequality on $a_n$ yields $$ a_n < q^{-n} j(\tau) < e^{2\pi n t} (e^{2\pi/t} + 1728). $$ The main term $\exp(2\pi (nt+1/t))$ is minimized at $t = 1/\sqrt{n}$ where it equals $\exp(4\pi \sqrt{n})$. Choosing this value of $t$ yields $$ a_n < e^{4\pi \sqrt n} + 1728 e^{2\pi \sqrt n} $$ which is an effective bound of the desired kind.

Postscript: one easy proof of $a_n>0$ starts from the formula $j = E_4^3 / \Delta$: the coefficients of $E_4$ are all positive, so the same is true for $E_4^3$; and $1 / \Delta = q^{-1} \prod_{m=1}^\infty ((1-q^m)^{-1})^{24}$ where each factor has nonnegative coefficients because $(1-q^m)^{-1} = \sum_{k=0}^\infty q^{km}$. So the product $E_4^3 \cdot 1/\Delta$ also has positive coefficients.

By a variation of Elkies's answer we can even get $a_n<e^{4\pi\sqrt{n}}$ without using $j(i)=1728$.

For $n=1$ the claim is clear. Now let $0<t<1$ and use the identity $j(it)=j(i/t)$. After expanding and rearranging, we get $$\sum_{n=1}^\infty a_n(e^{-2\pi nt}-e^{-2\pi n/t})=e^{2\pi/t}-e^{2\pi t}.$$ It follows that $$a_n<\frac{e^{2\pi/t}-e^{2\pi t}}{e^{-2\pi nt}-e^{-2\pi n/t}},\qquad n\geq 1.$$ Putting $t:=1/\sqrt{n}$, we get $$a_n<\frac{e^{2\pi\sqrt{n}}-e^{2\pi/\sqrt{n}}}{e^{-2\pi\sqrt{n}}-e^{-2\pi n\sqrt{n}}},\qquad n\geq 2.$$ so it suffices to show that the RHS is less than $e^{4\pi\sqrt{n}}$. Equivalently, $$4\pi\sqrt{n}-2\pi n\sqrt{n}<2\pi/\sqrt{n},\qquad n\geq 2,$$ $$2<n+n^{-1},\qquad n\geq 2.$$ The last inequality is obvious, so we are done.