Why is the Newtonian expression for kinetic energy called the "first order" approximation of the relativistic expression?
The way I see it, there are four possible answers. You can pick the one you like the most, because in the end it doesn't matter very much.
You're right, it's a second order approximation and those who say it's first order are making a terminology mistake.
When we say first order, we really mean first non-null order, since the linear term vanishes.
It's actually first order in $v^2$.
It doesn't really matter. We all know what the non relativistic approximation is, its properties are not going to change if we call it by a different name.
Personally I support answer 4, and I suggest you get used to it because physics is not known for its rigor and formality.
The issue of the terminology used for expansions has been pretty well addressed in Javier's response. I wanted to address another part of your question that you expressed concern about in a comment, namely your assertion that
we can see a much closer agreement for the approximation of kinetic energy than can be seen for linear momentum.
But in fact, the level of agreement between classical vs. relativistic values is actually worse for kinetic energy than it is for momentum at a given speed $v$. The only reason that the gap looks larger for the momentum in your graph is that the quantity itself is larger.
To see this, define $r$ to be the ratio of the relativistic value of some quantity to its classical value. For the momentum, this would be $$ r_p = \frac{mv \gamma}{mv} = \frac{1}{\sqrt{1 - v^2}} $$ (using units where $c = 1$), while for the kinetic energy it would be $$ r_\text{KE} = \frac{ m \gamma - m}{\frac{1}{2} mv^2} = 2 \frac{1/\sqrt{1 - v^2} - 1}{v^2}. $$ Plotting both of these, we get the following graph:
We can also plug in numbers to the above expressions. For example, at $v = \frac{1}{2}$, the relativistic momentum is $\frac{2}{\sqrt{3}} \approx 1.15$ times larger than the classical momentum, while the relativistic KE is $8(\frac{2}{\sqrt{3}} - 1) \approx 1.24$ times larger than the classical KE. The "ratio of the ratios", which we can think of as measuring the "relative badness" of the classical expressions for kinetic energy and momentum, is $$ \frac{r_\text{KE}}{r_p} = 2 \frac{1/\sqrt{1 - v^2} - 1}{v^2/\sqrt{1 - v^2}} = 2 \frac{ 1 - \sqrt{ 1 - v^2}}{v^2}. $$ This ratio approaches 1 in the limit $v \to 0$, which means that the classical expressions are "equally good" in this limit; and this ratio approaches 2 in the limit $v \to 1$, which implies that the classical expression for the kinetic energy is "twice as bad" in this limit.