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?

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.