One of the tough things about linear algebra is that it is just so damn useful for so many people that courses end up having a lot of compromises. And because of its pervasiveness, there are several good perspectives from which one should view the material.
For example, it's one of the first math courses to really teach algorithmic thinking. It's amazing to me just how much of elementary linear algebra you can prove just with Gaussian elimination. Various modifications of the classical algorithm are used to solve some heavy duty real world problems. Another example (although not so pervasive as Gaussian elimination) is the Gram-Schmidt process.
But I understand completely where you are coming from. Linear algebra is not just a set of tools to compute certain things -- it's a whole new way of thinking. To me, linear algebra makes a lot of sense when you think of it as capturing some basic ideas of geometry. Given an inner product, you have some very natural notions -- spheres, lines, hyperplanes, ellipsoids, etc. Linear transformations can be naturally thought of as geometric operations -- shears, rotations, inversions, etc. Some of the structure theorems for linear transformations have a geometric interpretation. One interpretation of the spectral theorem is if you have a symmetric operator A on a finite dimensional real vector space then this gives you a quadratic form f(t) = <t,At>. This function, restricted to the unit sphere, takes on a maximum value f(p) for some p, and it turns out that p is an eigenvector of A with eigenvalue f(p) (which is in fact the largest eigenvalue). You can get the next eigenvalue/eigenvector pair by considering the same maximization problem restricted to the orthogonal complement of f(p), and then keep repeating this, etc. This really blew my mind the first time I saw it, I'm pretty sure it's in Lang's Linear Algebra book. Another example of geometry coming in is the SVD... given any linear transformation, the image of a unit sphere under this transformation is an ellipsoid, and the lengths of the principal semi-axes are the singular values. Check wikipedia for the rest.
As for your remark about linear functionals, I'll chime in and say that one can naturally think of them as somehow measuring something. For example, the Riemann integral over some fixed set is a linear functional (on the vector space of riemann integrable functions). For a slightly different example, the Riesz representation theorem says that in any Hilbert space (complete inner product space. In finite dimensions, real or complex vector space have such a structure) a linear functional is of the form f(x) = <x,y> for some vector y, and intuitively you can imagine this as measuring (up to some scalar) the magnitude of vectors in the direction of y.