Why is cross product defined in the way that it is?

The cross product originally came from the quaternions, which extend the complex numbers with two other 'imaginary units' $j$ and $k$, that have noncommutative multiplication (i.e. you can have $uv \neq vu$), but satisfy the relations

$$ i^2 = j^2 = k^2 = ijk = -1 $$

AFAIK, this is the exact form that Hamilton originally conceived them. Presumably the choice that $ijk = -1$ is simply due to the convenience in writing this formula compactly, although it could have just as easily been an artifact of how he arrived at them.

Vector algebra comes from separating the quaternions into scalars (the real multiples of $1$) and vectors (the real linear combinations of $i$, $j$, and $k$). The cross product is literally just the vector component of the ordinary product of two vector quaternions. (the scalar component is the negative of the dot product)

The association of $i$, $j$, and $k$ to the unit vectors along the $x$, $y$, and $z$ axes is just lexicographic convenience; you're just associating them in alphabetic order.

If the right hand rule seems too arbitrary to you, use a definition of the cross product that doesn't make use of it (explicitly). Here's one way to construct the cross product:

Recall that the (signed) volume of a parallelepiped in $\Bbb R^3$ with sides $a, b, c$ is given by

$$\textrm{Vol} = \det(a,b,c)$$

where $\det(a,b,c) := \begin{vmatrix}a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \\ a_3 & b_3 & c_3\end{vmatrix}$.

Now let's fix $b$ and $c$ and allow $a$ to vary. Then what is the volume in terms of $a = (a_1, a_2, a_3)$? Let's see:

$$\begin{align}\textrm{Vol} = \begin{vmatrix}a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \\ a_3 & b_3 & c_3\end{vmatrix} &= a_1\begin{vmatrix} b_2 & c_2 \\ b_3 & c_3\end{vmatrix} - a_2\begin{vmatrix} b_1 & c_1 \\ b_3 & c_3\end{vmatrix} + a_3\begin{vmatrix} b_1 & c_1 \\ b_2 & c_2\end{vmatrix} \\ &= a_1(b_2c_3-b_3c_2)+a_2(b_3c_1-b_1c_3)+a_3(b_1c_2-b_2c_1) \\ &= (a_1, a_2, a_3)\cdot (b_2c_3-b_3c_2,b_3c_1-b_1c_3,b_1c_2-b_2c_1)\end{align}$$

So apparently the volume of a parallelopiped will always be the vector $a$ dotted with this interesting vector $(b_2c_3-b_3c_2,b_3c_1-b_1c_3,b_1c_2-b_2c_1)$. We call that vector the cross product and denote it $b\times c$.

From the above construction we can define the cross product in either of two equivalent ways:

Implicit Definition
Let $b,c\in \Bbb R^3$. Then define the vector $d = b\times c$ by $$a\cdot d = \det(a,b,c),\qquad \forall a\in\Bbb R^3$$

Explicit Definition
Let $b=(b_1,b_2,b_3)$, $c=(c_1,c_2,c_3)$. Then define the vector $b\times c$ by $$b\times c = (b_2c_3-b_3c_2,b_3c_1-b_1c_3,b_1c_2-b_2c_1)$$

Now you're probably wondering where that arbitrary right-handedness went. Surely it must be hidden in there somewhere. It is. It's in the ordered basis I'm implicitly using to give the coordinates of each of my vectors. If you choose a right-handed coordinate system, then you'll get a right-handed cross product. If you choose a left-handed coordinate system, then you'll get a left-handed cross product. So this definition essentially shifts the choice of chirality onto the basis for the space. This is actually rather pleasing (at least to me).

The other properties of the cross product are readily verified from this definition. For instance, try checking that $b\times c$ is orthogonal to both $b$ and $c$. If you know the properties of determinants it should be immediately clear. Another property of the cross product, $\|b\times c\| = \|b\|\|c\|\sin(\theta)$, is easily determined by the geometry of our construction. Draw a picture and see if you can verify this one.

Well, one can see the rule as is in order to agree with the standard orientation of $\mathbb{R}^3$ $(e_1 \times e_2=e_3)$. Or just convention.

There is a way to see how this can come up "naturally", though.

Given $a,b \in \mathbb{R}^3$, $a \times b$ is the vector which comes out from Riesz representation theorem (a fancy way to say that $V \simeq V^*$ using the isomorphism given by the inner product) applied to the linear functional

$$\det(\cdot, a,b).$$

Computing the vector yields both the fact that it has its norm being what it should be and its direction also being what it should be.

To get to the other direction, we would have to invert $a,b$, considering $a \times b$ to come from the vector corresponding to $\det(\cdot, b,a)$, an "unnatural" thing.

the Gibbs Vector Algebra Cross Product Right Hand Rule is a Convention

Any description of the (nominally) Euclidean 3 dimensional world we perceive runs into Chirality, the distinction between Right and Left handedness, the difference in a Mirror Reflection. https://en.wikipedia.org/wiki/Chirality

A Mathematical System describing this world has to have a Convention for coordinate order, orientation.
Justifications for the Right Hand Rule for the Vector Cross Product are a consequence of the choice of Chirality in the the "Standard Basis" and are circular, not deep - you just have to choose.

In fact the other choice has been used: http://web.stanford.edu/class/me331b/documents/VectorBasisIndependent.pdf

The right-hand rule is a recently accepted universal convention, much like driving on the right-hand side of the road in North America. Until 1965, the Soviet Union used the left-hand rule, logically reasoning that the left-hand rule is more convenient because a right-handed person can simultaneously write while performing cross products.