What's an intuitive explanation behind cross products being vectors, when dot products are not? As someone currently taking Multivariable Calculus but hasn't taken Linear Algebra, I've been trying to catch up on LA and build an intuition; simply knowing equations isn't really satisfying or useful.
My understanding of dot product and cross product (in $\mathbb{R}^3$) is that they generalize multiplication; whereas one becomes multiplication of the norms when vectors are parallel, the other (or rather, its magnitude) becomes multiplication of the norms when vectors are orthogonal. Dot product is maximized via similarity in the direction of vectors, whereas the magnitude of cross product is maximized by differences in the directions. This answer did a nice job at explaining that concept.
However, I'm still struggling to understand why cross products are vectors when dot products are scalars. The magnitude of cross product seems intuitive as an opposite to dot product, but I don't see how that is conceptually related to a vector being orthogonal to two others.
I've read answers like this to try and understand it, but I still don't see the relationship between measuring the directional difference between two vectors, and creating a new one perpendicular to the two vectors. How can I intuitively grasp that?
 A: Here's the way that I like to think about it: in $\Bbb R^3$, the dot product is used to give you information about the projection of one vector onto another and the cross product is used to give you information about the rejection of one vector from another.

Dot Product
If we have two vectors $\mathbf a$ and $\mathbf b$, what do we need to specify the projection $\operatorname{proj}_{\mathbf b}\mathbf a$?  We need the same things we need to specify any vector: a magnitude (length) and a direction.  Geometrically, we see that the magnitude of $\operatorname{proj}_{\mathbf b}\mathbf a$ is $\|\mathbf a\||\cos(\theta)|$ where $\|\mathbf a\|$ is the magnitude of $\mathbf a$ and $\theta$ is the angle between $\mathbf a$ and $\mathbf b$.  The absolute value of the cosine is there so that the formula continues to work for obtuse angles (make sure you understand that this formula works for all angles between $0$ and $\pi$ radians).
But what about the direction?  By definition, the direction of the projection will either be in the direction of $\mathbf b$ (acute angle) or in the direction of $-\mathbf b$ (obtuse angle).  Then note that we don't really need to use a vector to encode this information -- that would be overkill.  We could just use a sign ($+$ or $-$) to encode it.  Let's say that we want our product to be positive when the angle $\theta$ is acute and negative when $\theta$ is obtuse.  I.e.
$$\operatorname{proposed operation} = \begin{cases} \|\mathbf a\||\cos(\theta)|, & \theta \in \left[0, \frac{\pi}2\right] \\ -\|\mathbf a\||\cos(\theta)|, & \theta \in \left[\frac{\pi}2, \pi\right]\end{cases}$$
But here's the interesting thing, $\cos(\theta) = |\cos(\theta)|$ when $\theta\in\left[0, \dfrac{\pi}2\right]$ and $\cos(\theta) = -|\cos(\theta)|$ when $\theta\in\left[\dfrac{\pi}2, \pi\right]$.  So we can just replace this piecewise defined formula with the simpler
$$\operatorname{proposed operation} = \|\mathbf a\|\cos(\theta)$$
So then, we should define the dot product as just
$$\mathbf a \cdot \mathbf b = \|\mathbf a\|\cos(\theta)$$ right?  Actually, we get two very nice properties if we scale the right hand side (RHS) by the magnitude of $\mathbf b$: 
$$\mathbf a \cdot \mathbf b = \|\mathbf a\|\|\mathbf b\|\cos(\theta)$$
we get that $\mathbf a\cdot \mathbf b = \mathbf b \cdot \mathbf a$ (easy to see from symmetry of the RHS) and we get that this product is bilinear.  That may not make sense to you right now, but it is a very desirable property.  And notice that that extra factor doesn't impede our ability to reconstruct the projection at all.  In fact, you should confirm for yourself that
$$\operatorname{proj}_{\mathbf b}\mathbf a = (\mathbf a \cdot \hat {\mathbf b})\hat {\mathbf b}$$
where $\hat {\mathbf b} = \dfrac{\mathbf b}{\|\mathbf b\|}$.
Cross Product
The construction of the cross product is done very similarly, but the big difference is when we try to encode the directional information.  Remember that the rejection of $\mathbf a$ from $\mathbf b$ will be orthogonal (perpendicular) to $\mathbf b$.  But in $\Bbb R^3$, there are infinitely many directions orthogonal to $\mathbf b$.  So we can't just encode this information in a single scalar -- we'll need the cross product to result in a vector quantity.
If we want any semblance of the symmetry of the dot product, we also can't have the cross product just point in the direction of the rejection because then the direction of $\mathbf a\times \mathbf b$ would have no real relationship to the direction of $\mathbf b \times \mathbf a$.  Instead we need a way to encode the directions of both rejections together.  Luckily three-dimensional space has a useful property: every plane (containing the origin) is orthogonal to a unique line (containing the origin).  So then the clever idea is to construct a plane from $\operatorname{rej}_{\mathbf a}\mathbf b$ and $\operatorname{rej}_{\mathbf b}\mathbf a$ and then point the cross product in one of the two directions along the line orthogonal to that plane.  Then we've gotten our choice of infinitely many directions down to just two choices (one of two directions along the line).
Then we just need some way to always make a consistent choice.  The right hand rule is a (somewhat arbitrary) way to make such a choice.
One other thing to note (which you could try to prove) is that the plane spanned by $\operatorname{rej}_{\mathbf a}\mathbf b$ and $\operatorname{rej}_{\mathbf b}\mathbf a$ is exactly the same as the plane spanned by just $\mathbf a$ and $\mathbf b$.  So when defining the direction of the cross product vector, it's easier to do so in terms of $\mathbf a$ and $\mathbf b$ directly.
Then we can recover the rejection $\operatorname{rej}_{\mathbf b}\mathbf a$ from the slightly more complicated formula (due to the cross product actually being orthogonal to the rejection rather than pointing in its direction):
$$\operatorname{rej}_{\mathbf b}\mathbf a = \hat{\mathbf b}\times(\mathbf a\times \hat{\mathbf b})$$
which you can find by first showing that
$$\mathbf a \times \mathbf b = \operatorname{rej}_{\mathbf b}\mathbf a \times \mathbf b$$
Past the Motivations
The above "constructions" are really just one way to motivate the definitions, but you could still ask why for example we use a scalar instead of a vector in defining the dot product.  I hope I've convinced you that we don't need a vector, but there's nothing to suggest that we couldn't define it that way.  The reason actually comes from the parts I glossed over about the properties that we want the dot and cross products to have.  In particular, we want the dot and cross products to be invariant under certain transformations.  You can wait until you actually get to linear algebra to learn about that, but the headline is that the dot product will only have the required invariance property if it's a scalar quantity rather than a vector quantity.
Wedge Product
When motivating the cross product, I used a property of three-dimensional space.  This has a rather unfortunate consequence: the cross product (as a bilinear product from vectors to vectors) is only definable in three-dimensions (and weirdly in 7-dimensions, but we won't go into that construction here).  But there actually is a way to generalize the cross product to something that works in any dimension so long as we're willing to give up the property that it should result in a vector.  In fact, it can't result in a scalar either.  If we introduce new objects called bivectors, then we can get a much more elegant and general product called the wedge product.  It almost certainly won't be covered in your multivariable calculus course, or even in your future linear algebra course, but if you'd like to learn the very basics of it, I suggest reading through my answer here.  At the bottom, I give a couple of references from which you can learn more.
A: First, the dot product exists in $\mathbb{R}^n$ for all $n$, and has the same interpretation, and has a generalisation to any kind of vector spaces, and is an extremely powerful tool due to the so many different ways to compute it (using either coordinates, distances, angles, orthogonal projections). On the other hand, the cross-product is something really specific to $\mathbb{R}^3$.
This is in my opinion a hint that one should not try to think of these two objects as being similar, or try to understand them as parts of a whole, larger picture. The similarity stops at the cosine formula for the dot product versus the sine formula for the magnitude of the cross product.
Note that this question has received very good answers as to what the dot product is and how powerful it is.
On the other hand, the cross product is handy to provide normal vectors, provides a formula for the determinant of $3\times 3$ matrices and also much useful in mechanics. I'm probably missing some, but the point is: two different things.
Edit. Here is a very rough/intuitive explanation regarding the cross product versus orthogonality:
An orthogonal vector is one that will be as far as possible from being coplanar to the original vectors. You want $det(u,v,w)$ to be as far as possible from $0$. 
Note that $$\det \left[\matrix{x_u & x_v & a\\y_u & y_v & b\\z_u & z_v & c\\}\right]$$ 
is a linear combination of $a$, $b$, $c$ if you develop along the third column. There is one natural choice for $a$, $b$ and $c$ that will make this sum a sum of three squares, as far as possible from $0$ then, and this choice is the coordinates of the cross-product:
$$a=\det \left[\matrix{y_u & y_v\\z_u & z_v}\right],\qquad b=-\det \left[\matrix{x_u & x_v \\z_u & z_v }\right],\qquad c=\det \left[\matrix{x_u & x_v \\y_u & y_v }\right]$$
If with this choice the determinant is still $0$, then it's $u$ and $v$'s fault, we've done all we could.
A: The dot and cross products actually originated from doing algebra with the quaternions.
Similarly to the complex numbers, we can define the quaternions by taking three new "quaternion units" $i$, $j$, and $k$, and define the arithmetic so that
$$ i^2 = j^2 = k^2 = ijk = -1$$
Note, however, that multiplication is not commutative; it does not generally satisfy the identity $xy=yx$. For example, you have the multiplciation table
$$ ij = k \qquad jk = i \qquad ki = j$$
$$ ji = -k \qquad kj = -i \qquad ik = -j$$
Any quaternion can be written in the form 
$$ a + bi + cj + dk $$
where $a,b,c,d$ are real numbers. Given such a quaternion, define its scalar part to be $a$, and its vector part to be $bi + cj + dk$.
If you take the product of two vector quaternions, you get:
$$(x_0 i + y_0 j + z_0 k) (x_1 i + y_1 j + z_1 k)
\\=  -(x_0 x_1 + y_0 y_1 + z_0 z_1)
+ (y_0 z_1 - y_1 z_0) i  + (z_0 x_1 - z_1 x_0) j + (x_0 y_1 - x_1 y_0) k
$$
You can recognize that the negative of the scalar part and the vector part of this product are precisely the usual dot and cross product formulas.
