A good History of Math course would probably be enjoyable, and give you a good idea of what things are and where they lie.
From the mathematical point of view, Linear algebra is often a good "first advanced mathematics course", a good jumping-off point: it is still concrete enough that you won't get lost in a sea of abstraction (a possible issue with abstract algebra depending on how it is taught), cover entirely new ideas ("advanced calculus" can feel like you are just re-treading the same ground you already know, and depending on the specific topics analysis might also feel like it), but it should make you work through proofs and concepts in a way with which you probably have not done so far. In addition, linear methods will show up all over the place later on, so it would prove useful.
In that same vein, Number Theory can be a really good "first abstract course in mathematics", while sticking close to things you are very familiar with (the integers and rationals) while also probably delivering some exciting surprises. It often surprises a lot of people just how much of mathematics arises out of number theory (complex analysis and abstract algebra, to name just two).
If you want to stick to the applied side, differential equations is a good place to go as well. Linear algebra would be useful there, though.
So, I would suggest linear algebra or number theory first (if you can also get a good history of math course, do that as well), then decide if you want to go towards abstraction (in which case, head to abstract algebra, mathematical analysis, or whichever of linear algebra or number theory you did not take) or more towards applications (differential equations, a good advanced probability/statistics course, or a discrete mathematics course).
It is indeed the case that mathematics starts branching out, but some of the most interesting things happen where the branches meet; it would be ideal to be able to take a good one semester or one year sequence in the major areas (analysis, algebra, differential equations, topology, logic/set theory, number theory), then go on to more advanced courses in whichever area(s) you find interesting. But the truth is that this is very hard to do: not only would such a wide choice not be available except in the largest universities, but it would also mean a lot of your time. I did my undergraduate in Mexico, where all I did in college was mathematics courses, and it basically took six semesters before that had been covered (in addition to the calculus sequence, a linear algebra sequence, an abstract algebra sequence, a mathematical analysis sequence, differential equations, discrete mathematics, complex analysis, probability and statistics, plus some other stuff to "fill in the corners"; it would be barely possible to do it in two years if you are not taking the calculus sequence, but not if you are also taking other coursework as you would be in most institutions in the United States).
Several comments: I think that most "easy" abstract algebra books are well worth reading if you find an intermediate or advanced text too dense. I am not aware of any abstract algebra that is not "the real deal".
I wonder what the rest of your mathematics background is. My answer here would be affected if, say, this was the first "real" math course you ever took, or on the other hand if you had attended courses like real analysis or topology before this class.
If this is your first "real" class, there is the possibility you just haven't finished your habilitation phase moving from "calculus" type courses to "proof" type courses. For the first 12 years of school, US students are taught a lot of things in the mathematical curriculum which do not really represent mathematics properly. It is often a shock to adjust to the real thing. I would hope you might consider trying abstract type courses again, in this case :) Sometimes it takes getting used to. If this is the case, I don't know if you have the experience to say that the way things are taught should change.
If you have had "real" math classes before, then it's still possible you just don't have a very pedagogically oriented professor. It is often very hard to change the way one teaches, and several profs don't have the patience to do it. If you think your prof is pretty open, then it would be a fantastic idea to go talk to him about how the course went. He would probably be very happy to see you take such an interest in it. It might not result in an algebra revolution at your school, but it might make it a bit better for your peers!
Best Answer
A good reference for the theorem is the paper by Jean H. Gallier, "What's so special about Kruskal's theorem and the ordinal $\Gamma_0$? A survey of some results in proof theory." Ann. Pure Appl. Logic 53 (1991), no. 3, 199-260.
(With a short erratum in Ann. Pure Appl. Logic 89 (1997), no. 2-3, 275.)
I do not know of any (undergraduate) books where Friedman's result is discussed in any sort of detail, but this paper is very good.
For some background, you may also want to read the paper by Joseph B. Kruskal, "The theory of well-quasi-ordering: A frequently discovered concept." J. Combinatorial Theory Ser. A 13 (1972), 297–305.
Here is the review from MathScinet:
A good book to learn about well-quasi-ordering theory itself, from a logician's perspective, is "Recursive Aspects of Descriptive Set Theory" (Oxford Logic Guides), by Richard Mansfield and Galen Weitkamp. I think the level is fairly accessible. The chapter on wqo theory is by S. Simpson, who is a very good expositor.