I agree with much of what Spencer and NZS have said--that these folks selectively bred their horses for the qualities (both temperment and ability) that they valued, and they likely started with breeds that were most suitable to their activities/needs/desires. 

Various horse cultures throughout history have produced breeds that we now value for other reasons--Arabians were light, "easy keepers" who were strong, could go for long periods w/o water/food, and who had incredible endurance.  They were also smart and loyal.  Yet their point of origin had no special "alluvial silt" (I used a line like that in a poem once!) to help strengthen them en masse; it was more like years and years (centuries, even) of selective, knowledgeable breeding, taking only the best and breeding to the best for their needs and their context.

Similarly, European warmbloods have been been bred for centuries initially for calvalry work, but since have been "discovered" as incredible sport horses.  Americans have warmbloods, too, but they haven't been at it for centuries, thus their horses aren't as refined or targeted (for instance, Holsteiners tend to be great jumpers; Hannovarians excell at dressage; though both breeds can often cross over categories). 

The US does have breeds that have been selectively bred, though, for a while--NZS notes the morgan (likely a wamblood, a cross between a "cold blooded" draft horse and a "hot" horse like an arab), a "jack of all trades" animal the US produced (reminds me of the Welsh pony in a lot of respects), and the quarter horse (and I saw a LOT of these in my travels this past two weeks).  These horses are amazing--I've read a lot about quarter horses not being "good" at dressage, yet I watched/helped w/ a few roundups, and these horses dance on command better than any ballerina--the difference is they turn it off and on like lightening, depending on need, as opposed to more sustained dressage movements.

That said, I DO think the training they get at birth and beyond helps w/ their reputation.  Horses that are "imprinted" at birth (touched all over, etc.) briefly seem to be more amenable to later training.  My guess is that the horse culture of Rohan had not only gotten breeding down to a science, but also training down to a consistent, repetable pattern.

Not all those who wander are lost.