Dear Matthew, I have a couple of different remarks about the question and about the assumptions you seem to be making.
You write "I'm tempted to skip on to linear maps, matricies etc. which seems more interesting to me (and sort of motivates why we might care about choosing a different basis...)" But what do you mean by "different basis"? It seems to me that the main point of this kind of course that the students should take home is that there is no canonical choice of basis. You can only talk about "a different basis" if you have a god-given basis that the vector space is born with. But a vector space looks the same from all directions. If the students understand that, then they will accept that in describing e.g. elements of the space or linear maps, they have to make arbitrary choices, so the next natural question is "how do things depend on my choice?".
Once the students accept, that there is no god-given basis, I don't think that the Steinitz exchange lemma and the invariance of dimension will be as hard as you are expecting them to be. I wouldn't have thought, that you would need "weeks" (plural!) to prove that the size of a basis is an invariant of the vector space. And anyway, with enough pictures and the constant reminder that you are just investigating, how things depend on your arbitrary choices, they should be able to get the gist of the arguments even before they see the details.
You are saying that the students have had a first exposition to the algorithmic/practical aspects of linear algebra. So surely, it is time for them to learn, that you can develop the subject rigorously. The situation you are describing is not actually one, where you are "doing a linear algebra course in maximal abstraction early on". Neither is it early on, if it's a second course on linear algebra, nor does the fact that finite dimensional vector spaces have a well-defined dimension exactly signify maximal abstraction.
My summary: I think you should go ahead with the syllabus and think more about how to take their fears and make things intuitively clear than where to "cheat".
I hope this helps.