I'm teaching such a course at the moment, and whilst my university has high aspirations, I think that the "Not Quite Oxford" appellation applies here as well.

(For those who like the answer first, I pretty much agree with Alex and Robin.)

Here's the approach I'm taking:

1. Matrices are great, but dull.  They're fantastic for actually getting an answer, but doing all the manipulations yourself is fantastically boring and prone to error.  Fortunately, computers are really good at doing such manipulations and (as yet) don't get bored.  In summary, being able to use matrices is a really Good Thing but actually using them yourself isn't.

2. A matrix represents (note the word) a linear transformation from one Euclidean space to another.  There's an obvious and easy correspondence between the two.  So we can use everything we know about matrices to study linear transformations between Euclidean spaces.

3. But not everything we want to study is a linear transformation from one Euclidean space to another.  How about differentiation of polynomials (of some fixed finite order)?  It feels like we could do this with a matrix, but can we?

4. By considering this example, we decide that if we have an isomorphism from our arbitrary space to a Euclidean space, then we can use matrix methods.  So we _define_ "finite dimension" (as a whole concept) to mean "there is an isomorphism to some Euclidean space".

5. Using Gaussian Elimination (a la Robin), we can show that if $V \cong \mathbb{R}^n$ for some $n$ then $n$ is unique.  (No hand-waving required.)  This allows us to define the actual dimension.

6. So "finite dimension" means "can make it look like $\mathbb{R}^n$" which means "can use matrix methods".  But this approach brings to the surface the isomorphism $V \cong \mathbb{R}^n$ and so it's really easy to focus our attention on the question: "How do I choose between the different such isomorphisms?" (for example, $\operatorname{Poly}_3 \cong \mathbb{R}^4$ by coefficients, or by evaluation at $0,1,2,3$ or some other means).

7. Finally, for those die-hard basists, I _mention_ that an isomorphism $V \cong \mathbb{R}^n$ is *the same thing* as a(n ordered) basis of $V$.  This comes easily from the fact that giving a(n ordered) $k$-element subset of $V$ is the same as giving a linear transformation $\mathbb{R}^k \to V$, and then we observe:

   * $\mathbb{R}^k \to V$ injective if and only if $\{v_1,...,v_k\}$ linearly independent
   * $\mathbb{R}^k \to V$ surjective if and only if $\{v_1,...,v_k\}$ spanning
   * $\mathbb{R}^k \to V$ isomorphism if and only if $\{v_1,...,v_k\}$ basis

8. The meta-point of it all is that the students should think of an isomorphism $V \cong \mathbb{R}^n$ as a _point of view_: a way of looking at $V$.  So being able to change ones point of view to suit the circumstances is a very good skill.  And that applies as well to bases: thinking of a basis as a set of elements is useful for actually going out and finding one, but thinking of it as an isomorphism $V \cong \mathbb{R}^n$ is very good once you know it exists.

9. It's probably pretty obvious from the above, but I'll say it anyway.  In this, I *do* consider $\mathbb{R}^n$ to have an obvious choice of basis.  I mean, _I_'d choose it, wouldn't you?  There's also a bit of category theory sitting underneath all of this which recognises that $\mathbb{R}^n$ is the free vector space on $\{1,...,n\}$.  Also, later in the semester I'll talk about orthonormal bases of (separable) Hilbert spaces.  Only I won't, I'll talk about isometric isomorphisms $H \cong \ell^2$.

For more on how I'm doing this, you can look at my recent lectures: [here](http://www.math.ntnu.no/~stacey/Teaching/TMA4145h2010/lectures.html) and some other details on our course wiki, in particular at the page on [dimension](http://syvert.math.ntnu.no:2500/tma4145/show/dimension).

(On that, I don't think that _all_ information has to be given in lectures.  I think that students should be expected to fill in some gaps by themselves.  To forestall a slurry of comments about how I'm encouraging Bad Teaching Again, the gaps should be specifically chosen by the lecturer for this purpose rather than being what the lecturer happens to forget to say.)