Linear Algebra Texts?

I rather like Linear Algebra Done Right, and depending on the type of students you are aiming the course for, I would recommend it over Hoffman and Kunze. Since you seemed worried that Axler might be too advanced, my feeling is that Hoffman and Kunze will definitely be (especially if these are students who have never been taught proof-based mathematics).

Of course, the big caveat here being that Axler avoids determinants at all costs, and this will put more on you to introduce them comprehensively.

I've never looked at it, but another one worth considering might be Halmos's Finite Dimensional Vector Spaces.

Hands-down, my favorite text is Hoffman and Kunze's Linear Algebra. Chapter 1 is a review of matrices. From then on, everything is integrated. The abstract definition of a vector space is introduced in chapter 2 with a review of field theory. Chapter 3 is all about abstract linear transformations as well as the representation of such transformations as matrices. I'm not going to recount all of the chapters for you, but it seems to be exactly what you want. It's also very flexible for teaching a course. It includes sections on modules and derives the determinant both classically and using the exterior algebra. Normed spaces and inner product spaces are introduced in the second half of the book, and do not depend on some of the more "algebraic" sections (like those mentioned above on modules, tensors, and the exterior algebra).

From what I've been told, H&K has been the standard linear algebra text for the past 30 or so years, although universities have been phasing it out in recent years in favor of more "colorful" books with more emphasis on applications.

Edit: One last thing. I have not heard great things about Axler. While the book achieves its goals of avoiding bases and matrices for almost the entire book, I have heard that students who have taken a course modeled on Axler have a very hard time computing determinants and don't gain a sufficient level of competence with explicit computations using bases, which are also important. Based on your question, it seems like Axler's approach would have exactly the same problems you currently have, but going in the "opposite direction", as it were.

For teaching the type of course that Dan described, I'd like to recommend David Lay's "Linear algebra". It is very thoroughly thought out and well written, with uniform difficulty level, some applications, and several possible routes/courses that he explains in the instructor's edition. Vector spaces are introduced in Chapter 4, following the chapters on linear systems, matrices, and determinants. Due to built-in redundancy, you can get there earlier, but I don't see any advantage to that. The chapter on matrices has a couple of sections that "preview" abstract linear algebra by studying the subspaces of $\mathbb{R}^n$.