So roughly around the 18th century it became common, alongside introducing uniforms, to have a grooming standard in European (and later, American) militaries.
What confused me from paintings is that soldiers had a queue -- a sort of pony tail.
I know it fell out of favor and was replacesd by the high fade out of consern about headlice in the era of modern warfare, as well as being a hazard in close combat and with machinery.
But where did the idea of long-haired soldiers come from?
I think you're making a lot of assumptions here that are not entirely accurate.
[redacted misinformed statement about the term "queue"]
Now, uniforms were generally introduced around the time period you're talking about together with what was known as the regimental system. While this did mean that soldiers of the same army would have uniforms that were reasonably similar, in broad strokes, there was also quite a bit of leeway given to the colonel of each regiment in determining the uniform style- including, among other things, hair.
So, if a colonel wanted his men to wear their hair brushed back in a ponytail, they would, and if he thought curls were better, then they'd do that instead. What each colonel chose to do would be much less a reflection on military standards than general hairstyles for men of the time, which back then meant relatively long hair.
Now, concerns about lice or getting caught in things were certainly not why this type of hairstyle fell out of favor. It's generally hard to pin down historically why, exactly, styles changed, but in the case of military haircuts, Napoleon's military reforms marked the real change from longer to shorter. The revolutionary and imperial armies of France broke out of the aristocratic regimental model into a more centralized and standardized divisional system, and long hair was associated with the ancien regime, so they switched to shorter haircuts (for most troops- some elites retained the older styles) and the rest of Europe soon followed suit. This definitely wasn't a high fade, though- the now-standard military buzz cut wouldn't show up until well into the 20th century.