This is a somewhat long discussion so please bear with me.  There is a theorem that I have always been curious about from an intuitive standpoint and that has been glossed over in most textbooks I have read.  Quoting Wikipedia, the theorem is:


  The gradient of a function at a point is perpendicular to the level set of $f$ at that point.


I understand the Wikipedia article's proof, which is the standard way of looking at things, but I see the proof as somewhat magical.  It gives a symbolic reason for why the theorem is true without giving much geometric intuition.

The gradient gives the direction of largest increase so it sort of makes sense that a curve that is perpendicular would be constant.  Alas, this seems to be backwards reasoning.  Having already noticed that the gradient is the direction of greatest increase, we can deduce that going in a direction perpendicular to it would be the slowest increase.  But we can't really reason that this slowest increase is zero nor can we argue that going in a direction perpendicular to a constant direction would give us a direction of greatest increase.

I would also appreciate some connection of this intuition to Lagrange multipliers which is another somewhat magical theorem for me.  I understand it because the algebra works out but what's going on geometrically?

Finally, what does this say intuitively about the generalization where we are looking to: maximize $f(x,y)$ where $g(x,y) > c$.

I have always struggled to find the correct internal model that would encapsulate these ideas.

The gradient of a function is normal to the level sets because it is defined that way.  The gradient of a function is not the natural derivative.  When you have a function $f$, defined on some Euclidean space (more generally, a Riemannian manifold) then its derivative at a point, say $x$, is a function $d_xf(v)$ on tangent vectors.  The intuitive way to think of it is that $d_xf(v)$ answers the question:

If I move infinitesimally in the direction $v$, what happens to $f$?

So $d_xf(v)$ is not itself a tangent vector.  However, as we have an inner product lying around, we can convert it into a tangent vector which we call $\nabla f$.  This represents the question:

What tangent vector $u$ at $x$ best represents $d_xf(v)$?

What we mean by "best represents" is that $u$ should satisfy the condition:

$\langle u,v\rangle  = d_xf(v)$ for all tangent vectors $v$.

Now we look at the level set of $f$ through $x$.  If $v$ is a tangent vector at $x$ which is tangent to the level set then $d_xf(v) = 0$ since $f$ doesn't change if we go (infinitesimally) in the direction of $v$.  Hence our vector $\nabla f$ (aka $u$ in the question) must satisfy $\langle\nabla f, v\rangle = 0$.  That is, $\nabla f$ is normal to the set of tangent vectors at $x$ which are tangent to the level set.
For a generic $x$ and a generic $f$ (i.e. most of the time), the set of tangent vectors at $x$ which are tangent to the level set of $f$ at $x$ is codimension $1$ so this specifies $\nabla f$ up to a scalar multiple.  The scalar multiple can be found by looking at a tangent vector $v$ such that $f$ does change in the $v$-direction.  If no such $v$ exists, then $\nabla f = 0$, of course.
