If you are looking for a gentle introduction, that uses matrices from the beginning, I would suggest you consider "Linear Algebra" by Friedberg, Insel and Spence. I haven't used this book myself, but somebody (I trust) recommended this book to me. I now own it, and it looks very nice and gentle (but covering all the topics I would like to include), and matrices are introduced in page 8.

Alvaro