> Even the "why does matrix multiplication look that way" is incredibly deep but practically impossible to motivate from other considerations. You just start with "well that's the way it is" and grind away

In my experience it need not be like that at all.

One can start by defining and demonstrating linear transformations. Perhaps from graphics -- translation, rotation, reflection etc. Show the students that these follow the definition of a linear transformation. That rotating a sum is same as summing the rotated(s).

[One may also mention that all differentiable functions (from vector to vector) are locally linear.]

Then you define adding two linear transformations using vector addition. Next you can define scaling a linear transformation. The point being that the combination can be expressed as linear transformations themself. No need to represent the vectors as R^d, geometric arrows and parallelogram rule would suffice.

Finally, one demonstrates composition of linear transformations and the fact that the result itself is a linear transformation.

The beautiful reveal is that this addition and composition of linear transformations behave almost the same as addition and multiplication of real numbers.

The addition asociates and commutes. The multiplication associates but doesn't necessarily commute. Most strikingly, the operations distributes. It's almost like algebra of real numbers !

Now, when you impose a coordinate system or choose a basis, the students can discover that matrix multiplication rule for themselves over a couple of days of playing with it -- Look, rather than maintaining this long list of linear transformations, I can store it as a single linear transformation in the chosen basis.