I have taught Linear Algebra a few times, at both basic and advanced levels, and the introductory text which served me best for precisely the goal the OP is aiming is, surprisingly, the first five chapters of the second volume of the late Tom M. Apostol's classic Calculus. It is a concise, no-nonsense and down-to-earth first course in linear algebra which starts from abstract vector spaces right at the first chapter (with lots of examples, of course) and moves to matrices in the second chapter right after introducing linear transformations. I find Apostol's approach quite refreshing because it greatly illuminates the matrix operations involved in solving linear systems (Gauss-Jordan elimination, etc.).
Notice, though, that this is really a first encounter with linear algebra, so only real vector spaces are discussed and a tad more advanced topics like the Jordan canonical form are not treated. For the latter, I agree with The Mathemagician's answer that a purely algebraic approach might not be advisable to a broader audience. For instance, I particularly enjoy Filippov's proof of the Jordan canonical form using matrix exponentials as fundamental solutions to linear autonomous ODE systems, which is the one used in G. Strang's Linear Algebra and its Applications. Such an argument would fit perfectly in Chapter 7 (on linear ODE systems) of Apostol's volume, where matrix exponentials are discussed in depth (including Putzer's algorithm, presented as an application of the Cayley-Hamilton theorem), so in retrospect I feel somehow it was a missed opportunity.
