Let me take a stab at the intuition behind the definition of the cross-product.
First, note that cross-product is a construct that is specific to three dimensions (it can technically be defined in seven dimensions too, but there, this construction is not unique). Let's first see what is special about three dimensions. The idea is to define a binary operator that takes two vectors and produces another one. Two (non-parallel) vectors define a plane, and only in three dimensions, the direction and orientation of a $2$D-plane can be uniquely determined by a vector perpendicular to it. That is, in $3$D there is a natural map between planes through the origin (defined by pairs of non-parallel vectors) and vectors up to a scalar multiple. In higher dimensions, for every $2$D-plane, there are multiple non-parallel vectors that are perpendicular to the plane, and for every vector, there are multiple planes passing through the origin that are perpendicular to that vector. Therefore, there is no natural (unique up scaler multiple) mapping between planes through the origin (read pair of vectors) and vectors in higher dimensions.
This duality between planes and vectors perpendicular to them in $3$D allows us to identify otherwise-more-complicated-mathematical-objects with vectors (which we know have nice properties), and that is the main motivation behind defining cross product. There are two examples of such objects that I think best motivate the definition of cross-product (1) surface area and (2) rotation. The first one is mentioned by the OP and is the subject of the first question, and the second one is really the motivation behind the application cross-product in the magnetic field which is again mentioned by the OP. Let us start with the surface area:
Cross Product as Area Element
I am going to motivate this using the following example. Suppose you have a continuous fluid moving with some velocity field $\vec v(\vec r)$ in $3$D space. And suppose you have a surface area (possibly curved) and you want to know how much fluid is going through this surface per unit time. Obviously, if the velocity field is completely parallel to the surface, the fluid is not going through it, so it is not hard to convince yourself (draw a picture) that the flux density of the fluid through the surface is given by the component of $\vec v$ perpendicular to the surface. So the total flux would be given by the integral of the perpendicular component of $\vec v$ on the surface.
Since the direction of the surface everywhere can be determined by its normal vector $\hat n$, we can find the net flow rate through the surface as
$$
\text{Flow rate}=\int_{\text{surface}}\vec v \cdot \hat n \,dS
$$
Let us parametrize this surface with two parameters $s$ and $t$ such that all the points on the surface can be written as $\vec r=(x(s,t),y(s,t),z(s,t))$. At every point with parameters $(s,t)$ on the surface, the two vectors $\partial \vec r/\partial s$ and $\partial\vec r/\partial t$ are tangent to the surface. Then the normal vector to this surface is parallel to the cross-product of these two vectors. Fortunately for us, the area element $dS$ is also proportional to the length of the cross product so that we can write the combination $\hat n\, dS$ as
$$
\hat n\,dS = \frac{\partial \vec r}{\partial s}\times \frac{\partial \vec r}{\partial t} dt\,ds.
$$
This allows us to reduce the surface integral to an ordinary double integral on the coordinates $s$ and $t$:
$$
\text{Flow rate}=\int_{\text{surface}}\vec v \cdot \hat n \,dS = \int\int\vec v(s,t) \cdot \left(\frac{\partial \vec r}{\partial s}\times \frac{\partial \vec r}{\partial t} \right)\,ds\,dt.
$$
What made this problem easy is that the area element which is defined by the pair of vectors $(\partial \vec r/\partial s,\, \partial\vec r/\partial t)$ can be identified by a vector such that when we need to find the component of $\vec v$ normal to the surface, we simply took the dot product of $\vec v$ by the area element. If we did not have the luxury of identifying the area element as a single vector, we would have to manually find the component of $\vec v$ that is perpendicular to both vectors defining the surface.
Note that this area element is the promised otherwise-more-complicated-mathematical-object that only in $3$D can be identified by a vector. In higher dimensions, this beast is known as the wedge product of the two vectors defining it and cannot be reduced to a single vector.
Cross Product as Rate of Rotation
We tend to think of proper rotations in $3$D in terms of an axis of rotation and an angle. The concept of the axis of rotation does not generalize to higher dimensions. What does generalize is the plane perpendicular to it. This plane perpendicular to the axis of rotation is invariant (it gets mapped to itself) under rotation. Higher-dimensional proper rotations can be identified in terms of the set of their invariant planes and the angles of rotations associated with each plane. It is the duality between planes and axes (map between a pair of vectors and a single vector perpendicular to them) that allows us to talk about the axis of rotation in $3$D.
Imagine rotating a vector $\vec v$ at the rate of $\omega$ radians per second around an axis of rotation defined by the vector $\hat u$ perpendicular to some plane $P$. Since $P$ is the rotation plane, if we decompose $\vec v$ to its components $\vec v_\perp$ and $\vec v_{||}$, perpendicular and parallel to the plane $P$, $\vec v_\perp$ will not change under the rotation, while $\vec v_{||}$ stays in $P$ and rotates at the rate $\omega$. So the rate of change of $\vec v$ is given by the rate of change of $\vec v_{||}$. Since $\vec v_{||}$ is now in a $2$D plane, we can rewrite its rate of change in polar coordinates
$$
\frac{d\vec v}{dt} = \frac{d\vec v_{||}}{dt} = \frac{d\left|\vec v_{||}\right|}{dt}\hat r+\left|\vec v_{||}\right| \omega\, \hat\theta = \left|\vec v_{||}\right| \omega\, \hat\theta
$$
Here I used $d\vec r/dt = \dot r\hat r+r\dot\theta\hat\theta$ (see here) and the fact that rotation does not change the length of a vector. Without using the axis of rotation $\hat u$ it would be hard to find both $\left|\vec v_{||}\right|$ and the direction of $\hat\theta$ (which is on the plane $P$ and perpendicular to $\vec v_{||}$). But note that $\hat\theta$ is in the plane $P$, that is it is also perpendicular to $\vec v_\perp$ which makes it perpendicular to $\vec v$. Additionally, it is perpendicular to $\hat u$ since $\hat u$ is perpendicular to $P$. And since we know something that is perpendicular to two vectors is parallel to their cross product, $\hat \theta$ is in the direction of $\hat u\times \vec v$. Also $\left|\vec v_{||}\right|$ is $\left|\vec v\right| \sin(\phi)$ where $\phi$ is the angle between $\vec v$ and $\hat u$, so we can write the rate of change of $\vec v$ as
$$
\frac{d\vec v}{dt} =\omega\, \hat u\times \vec v
$$
Again, since we have a direction $\hat u$ and a scaler $\omega$ for the rotation, we can define a vector $\vec \omega = \omega\, \hat u$ as a rotation vector (really angular velocity vector) and say
$$
\frac{d\vec v}{dt} =\vec \omega\times \vec v.
$$
So if we identify rotations by vectors representing their axis of rotation and rate of rotation (rate of change of angle), the rate of change of any vector $\vec v$ under such rotation is given by the cross product of these two vectors. In other words, the cross product is the so-called infinitesimal generator of rotaions.
Here, the rotation is the promised otherwise-more-complicated-mathematical-objects that in three dimensions can be identified with the vector $\vec \omega$, and it simplifies the calculation of the rate of change of another object under the rotation.
But if $\vec \omega$ is that object, it should be the cross product of two vectors, and indeed it is. Just take a unit vector in the plane $P$ (let's call it $\hat r$). Its rate of change under this rotation is given by $\omega\, \hat \theta$. The vector $\vec \omega$ is simply the cross product of $\hat r$ and its rate of change. You can see that by noticing that $\hat r$ and $\hat \theta$ are perpendicular vectors in the plane $P$, and their cross product is simply the unit vector $\hat u$ perpendicular to $P$ so
$$
\hat r \times \frac{d\hat r}{dt} = \hat r\times\omega\, \hat \theta = \omega\, \hat u = \vec \omega.
$$
In other words, without the cross product, we would have to define rotations using these two vectors, $\hat r$ and $d\hat r/dt$ which would define both the plane of rotation and the rate at which a unit vector in that plane changes.
Magnetic Field as Axis of Rotation
The electric field is a very intuitive concept compared to the magnetic field. The magnitude of the electric field is the force per unit charge, and its direction is the direction of that force. So the electric field simply is force per unit charge. On the other hand, the magnetic field is a vector that if you take its cross product with $\vec v$ (the velocity of a moving test charge) would give you a force per unit charge. It does not seem to point to a physically meaningful direction in the space. Moreover, if you think about how it is created, it is produced through another moving charge (this is not always strictly true, but a moving charge does create a magnetic field). The magnetic field created by a moving charge with the velocity $\vec u$ at position $\vec r$ is proportional to $\vec r \times \vec u$. That gives a magnetic force on another moving test charge that is in the direction of $\vec v \times (\vec r \times \vec u)$ which is back in the plane defined by $\vec r$ and $\vec u$.
It seems like the direction of the magnetic field which points outside of the plane defined by $\vec r$ and $\vec u$ where all the action is happening is not really pointing at some physically meaningful direction in the space. It is a mere mathematical convenience to define it in that direction. But I encourage you to go back and read the previous section about the rotation to see the similarities.
A moving charge at position $\vec r$ with velocity $\vec u$ creates a rotating force at the origin attempting to rotate the velocity vector of any charge at the origin in the $\vec r$-$\vec u$ plane. But since in $3$D we can identify rotations with their axis instead of their plane, which we love to do because vectors are simpler mathematical objects with known rules than planes, we define this force in terms of a vector $\vec B$ that points outside of this plane. That is the magnetic field. And since the rate of rotation is given by the cross product of the rotation vector by the vector, the rate of change of the velocity $\vec v$ of a test charge at the origin is given by $\vec B\times \vec v$.
Now let me attempt to actually answer OP's questions
- Why wasn't the cross-product defined as just this magnitude? Was the orthogonal vector just some convenient form of killing two birds with a stone (getting both the measure of perpendicularity and getting the normal vector to the plane spanned by $a$ and $b$)?
As I mentioned already, the cross product, whether it represents an area element or rotation, is a property of two vectors, and you need the direction of the plane defined by them to have a full description of the mathematical object you are describing. In the case of area, we needed them that to find the component of velocity perpendicular to the surface, and in the case of rotation, we obviously need to know the axis of rotation. It is easier to work with one vector than it is to work with the two original vectors because the rules of vector algebra make it easier to calculate things in terms of coordinates, like the dot product in area calculation, or finding the rate of change of rotating vector instead of using a full rotation matrix.
- Is there any intuition that the components of cross product $a \times b$ are:
$ \langle(a_y b_z - a_z b_y), (a_z b_x - a_x b_z), (a_x b_y - a_y b_x) \rangle$?
Let us think of $a\times b$ as the rate of change of $b$ under a rotation $a$. Since the cross product is linear, we separate this as the sum of three independent rotations of $b$ around components of $a$. Let us look at the component $a_z$. That is a rotation around the $z$ axis. The rate of change of $b$ due to rotation around the $z$ axis is only affected by its projection on the $x-y$ plane, i.e. only $b_x$ and $b_y$ components. Rotating the projection of $b$ on $x$ around $z$ creates components along the $y$ direction while rotating the projection of $b$ along $y$ around z creates components in the $-x$ direction. So the rate of change of $b$ due to rotation at the rate $a_z$ around $z$ is given by
$$
(-a_z\,b_y,\, a_z\, b_x,\,0).
$$
Repeat the same logic for rotation around $x$ and $y$ at rates $a_x$ and $a_y$. Those would cause changes of $(0,\, -a_x\,b_z,\, a_x\,b_y)$ and $(a_y\,b_z,\, 0,\, -a_y\,b_x)$ to the vector $b$ respectively. Adding up all the changes, we arrive at the componentwise cross-product defined above.