It is a mistake to use matrices immediately in linear algebra for several reasons, even if they are (incorrectly!) regarded as central to linear algebra.
The general concepts are actually easier to understand without discussion of matrices, and most of the important results are simpler and easier to prove without reference to matrices.
Matrices are a useful computational tool in the case of finitely generated vector spaces, but they are not natural. That is why there are different rules for transforming matrices, depending on whether they represent linear transformations or bilinear forms. Matrices also hide te fact that calculus is nothing more or less than linear algebra, but with infinitely generated vector spaces.
If I were to recommend a single book for a first course, it would be K. Jänich's Linear Algebra, which is a first semester first year text for German students of mathematics and/or physics. It is thoroughly modern and readable.
