I think that "Introduction to Linear, Ideas and Applications" by Richard Penney might be exactly what the questioner is looking for. It is relatively gentle and it does integrate vector spaces and matrix algebra from the get go. When we have used this text the question of "what is a vector space" has never been an issue.

I apologize for plugging my own text, but I think that "Introduction to Linear, Ideas and Applications" by Richard Penney might be exactly what the questioner is looking for. It is relatively gentle and it does integrate vector spaces and matrix algebra from the get go. When I have taught from it the question of "what is a vector space" has never been an issue.