Why is the gradient always perpendicular to level curves?

First of all, when dealing with more than two variables level set is a better denomination than level curve (or level surface in three dimensions.)

Now to your question. Let $x_0\in L(c)$ and let $\gamma\colon(-a,a)\to \mathbb{R}^n$ be a $C^1$ curve contained in $L(c)$ and such that $\gamma(0)=x_0$. Then $$ f(\gamma(t))=c,\quad -a<t<a. $$ Differentiating with respect to $t$ and evaluating at $t=0$ we get $$ \nabla f(x_0)\cdot\gamma'(0)=0. $$ The set of all vectors $\gamma'(0)$ for all possible curves $\gamma$ forms the tangent hyperplane to $L(c)$ at $x_0$, and $\nabla f(x_0)$ is orthogonal to all of them, that is, the gradient is orthogonal to the tangent hyperplane of the level set.