Normal vector to a surface I've been reading in my calc book that the gradient vector is always orthogonal to the surface. 
So for a surface in space described by the level surface $f(x,y,z) = k$ where $k$ is a constant, $\nabla f$ is orthogonal to the surface at every point because the gradient is the normal vector of the surface at every point.
Then later I read about parametric surfaces where a surface is described by vector valued function $r(u,v) = <x(u,v), y(u,v), z(u,v)>$ and a normal vector $r_u \times r_v$ or $r_v \times r_u$
How are $r_u \times r_v$ and $\nabla f$ related here? I am referring to James Stewart's Text.
Also a last comment I want to make is, what about a normal vector to a surface that doesn't need to be described by a level surface? For example $f(x,y) = z = x^2 + y^2$? How would I go finding the normal vector at any point without rewriting it as $z - x^2 - y^2 = 0$ or parametrizing it?
A final Remark: I've been confusing the notion of the gradient vector being tangent to a surface instead of normal to it. There is this rather confusing picture I have which seems to suggests that the gradient vector really is tangent to a surface rather than normal because the gradient is formed by the vector sum of $\partial/\partial x$ and $\partial/\partial y$ and according to the picture I have, both $\partial/\partial x$ and $\partial/\partial x$ are "flat" and their sum should also be "flat" and not "pointing up"
Added PIcture

 A: These methods are just applications of two different geometric ideas to help you find a normal vector to a surface.  I'm sure that you or I could do some variable pushing and prove that they are compatible, but I don't know how enlightening that would be.  I think the most important thing is just to understand the geometry behind each of these ideas.
When you have a parametrized surface $r(u,v) = \left< x(u,v), y(u,v), z(u,v) \right>$ and a point $(u_0,v_0)$, you can consider two cross sections of that surface.  The functions $$r(u_0,v) = \left< x(u_0,v), y(u_0,v), z(u_0,v) \right>$$
$$r(u,v_0) = \left< x(u,v_0), y(u,v_0), z(u,v_0) \right>$$
define curves in three dimensions which are contained in the plane $r(u,v)$.  Convince yourself that a tangent vector to any curve contained in a surface is also tangent to the surface itself.  Therefore the vectors
$$  \frac{\partial}{\partial v} r(u_0,v) \big|_{v=v_0} $$
and
$$  \frac{\partial}{\partial u} r(u,v_0) \big|_{u=u_0} $$
are both tangent to the surface at $r(u_0,v_0)$.  Convince yourself that if these two vectors were parallel, then $r$ wouldn't look like a curve at this point, rather than a surface, so they should not be parallel.  In linear algebra terms, these vectors span the space of tangent vectors.  Their cross product will yield a vector which is normal to both of them, and therefore normal to the plane.  This is the definition you stated.
The other definition uses the fact that the gradient of a function at a point is perpendicular to the level surface at that point.  To understand this, it is helpful to think of the lower dimensional analogy.  The gradient of a function $f(x,y)$ (which defines a surface) will be perpendicular to the level curve at any point.  This is geometrically obvious if $f(x,y)$ defines a plane.  The level curve will be a horizontal line, and the gradient will point in the direction of greatest slope of the plane.  The same logic works, in fact, for $f(x,y)$ that is not a plane because the differentiability of $f$ tells us that it behaves like a plane at any given point.
A: It sounds like $f$ is a scalar field.  In that case, I would politely suggest looking at the gradient as simply being a vector field that, at any point, is orthogonal to some level surface of $f$.
When a surface is given parametrically, the normal vector is indeed $r_u \times r_v$.  The key here is understanding that $f$ as you've given it does not describe just a surface.  It describes a scalar field that permeates some domain (some volume).  It is of course possible to rewrite it is a level curve of a scalar field, but they're not really the same thing.  If you construct a scalar field in some way such that the parametric surface is a level surface of that field, then naturally the gradient will have the same direction as $r_u \times r_v$.
The same goes for your question about $z = f(x,y)$.  This also is a parametric description of a surface.  It's not obvious how to convert this into the level curve of some scalar field, so using the gradient seems clumsy--outside of writing it as the trivial level curve of $z-x^2-y^2=0$.  Basically what you're doing when you do that is constructing a scalar field from the parametric description and then looking at the level surface where that scalar field is zero.
Gradient vectors are normal to the level surfaces.  That's just fact.  Without seeing your picture, I can't really comment on how to correct your interpretation of this sketch.
