I think that, if I got hold of someone who knew no algebra, I would try to teach them rings and modules (together with linear algebra) rather than group theory. The basic reason is that in any kind of "application" (both applied math and applications of algebra to other theoretical math) one always seems to end up linearizing. Even in applications of group theory, especially to field theory, this is true; in fact, groups often come with a natural representation. The most important groups are linear groups.
The other reason for valuing ring theory is that it is more general. The basic group theory course is misleading in its emphasis on convenient consequences of finiteness, and it is also burdened with technical complications related to noncommutativity (of course, the study of finite abelian groups is part of the study of modules, as Jim said. There is a good case for spending time on that in the middle of the beginning of a rings course).
But what about Galois theory? It really ties the whole thing together; using a Galois theory course as an introduction to groups would be fascinating. However, the basic ideas are founded in linear algebra and to do any constructions you need to know basic ring theory. The linear algebra dependence is not strong; it is no stronger than the need to define groups before defining rings (which you really don't need to do), but the idea of having elements of the field act on the field itself as a vector space is not a comfortable one for beginners.
Perhaps viewing Galois theory as an application is itself problematic. It's a higher level theory; as Jim says in the question, people do not solve polynomials symbolically so much in applications. Galois theory is the sort of course you should show people who are on the theoretical track and who have the experience to see it for what it is. However, for a first algebra course I think that rings and modules with linear algebra should come first, followed by groups via some form of representation theory, possibly something with connections to analysis (I was never taught any use of algebra in analysis though I know it exists). Analysis is a big field.
For all its beauty, Galois theory is something of a niche product. There is no right choice here (really, dropping Galois theory seems morally wrong) but it is also worth remembering that it doesn't take a miracle to get students excited about math when they are already in a graduate algebra course. Representation theory is also very appealing (and for a similar reason, in fact), and a solid if utilitarian algebra course is very satisfying.
