Why is the time rate change of unit vector given by the angular velocity vector crossed with the unit vector?

The interpretation is simple. In a rotating frame, a fixed vector changes over a small time slice by an amount perpendicular to the vector and the rotation direction.

$$ {rm d}hat{u} = ( vec{Omega} {rm d}t) times hat{u} $$

or

$$ frac{{rm d}hat{u}}{{rm d}t} = vec{Omega} times hat{u} $$

I will not be going into math here as you want physical intuition. Unit vectors express a direction. Loosely speaking, you can think of a unit vector to be synonymous to direction or rather a mathematical analogue of the word 'direction'. So we can make the following comment, if you do not change your direction, your unit vector do not change. But if you do change your direction during your motion, the unit vector change changes. If you agree with the last statement, then let us understand, why change of direction is connected to rotation.

We measure curvature of any curve in terms of radius of curvature. This radius is the radius of a circle that is tangent to the curve under consideration. If the curvature changes at different points, then we require multiple circles of different radius to define the radius of curvature and as a result the radius of curvature may vary from point to point depending on the curvature. Now clearly, if we move along a part of a circle, then we are experiencing rotation. So, when we move along some curve, we will experience rotation, due to the curvature of the curve. The rotation is more when the curvature is more or in other words, thus the radius of curvature is small. (curvature is inversely proportional to radius of curvature)

Now, a straight line also a curve. So this must also be a part of a circle. This is true but the radius of the circle is infinite. Thus the radius of curvature is infinite as well and the curvature of a straight line is zero. Since the radius is infinite, we do not experience any rotation while moving along a straight line and thus our unit vector do not change either.

As mentioned earlier, changing direction means change in unit vector. But if we change direction, then we are moving along a curve that is not a straight line and thus, the radius of curvature is finite. This means, changing direction means, we are moving along some part of a circle. Thus, changing direction must be related to rotation right?

You can think of this as a physical reasoning behind why change in unit vector is related to rotation.

Now, about the cross product:

I guess you know, that the quantity $Omega times hat{u}$ is perpendicular to both $Omega$ and $hat{u}$. The direction this cross product implies, is along the tangent of the circle, of which the curve is a part of. Clearly, this tangent is the direction of the changing unit vector. This is why taking cross-product with $Omega$ (the angular velocity vector) is justified.

Hope this clarifies things.