Assuming that the Norse leave behind a castaway who teaches some tribes how to ride and make saddles, reigns, etc.
The spread of the Domestic horse was lightning fast in the West IOTL-less than 150 years between the first Spanish conquest of the Pueblo and the spread of domestic horses to Montana. However, the Plains are ideal horse territory, and the bison-hunting cultures already indigenous to the area lent themselves well to horsemanship. The northeast is much more hostile to horses, and maize growing people who farm by hoeing will probably not become defined by horses to the extent that the Plains Indians were.
Nonetheless, the usefulness of the horse has a pack animal and the mobility it gives will see it adopted, though they will be liable to be used as much as for food and hide as animals to ride. From the northeast it will spread slowly, but once it hits the southern shores of the Great Lakes, they come into traveling distance to the grasslands of southern Ohio/Kentucky, which is good horse country and at the time would have a healthy buffalo and deer population which could be hunted from horseback. From there, the horse is linked into the Mississippian cultural spheres, and trade will probably see them diffuse pretty rapidly as far south as the Gulf and east onto the plains, where I think we can expect similar migrations and disruptions as seen IOTL when the horse cultures rose. In the east though, the presence of a large beaver population and the wetlands they create means that cavalry is not quite so useful as it was in, say, OTL's Civil War era. Past the Rockies, the hunter-gatherer peoples there will probably be pretty hesitant to adopt horses as this will require too great a change in their lifestyle (which made them hesitant to adopt horses IOTL-while the Comanche were raising hell on the Southern Plains, their cousins in California mainly interacted with horses by stealing and eating them). There are a few potential drivers that could change this: cavalry raids from settled peoples to the east, ecological disruption from feral horses that consume edible wild plants, and in the Northwest where hierarchical societies existed, the bragging rights for owning an exotic creature.
I don't know if domestic horses could diffuse across the Mexican deserts in this 500 years. Yes, the Ancient Pueblo did trade with Mesoamerica, but the Ancient Pueblo society will probably be in the middle of its collapse when horses finally diffuse to them (if this is not sped up by hostile peoples now on horseback). Supposedly Moctezuma had a pet bison, so perhaps elite Mesoamericans could acquire horses as curiosities but in this scenario I don't think there's a lot of time for the horse to become an ingrained part of their culture-and at this point in time, the founder effect would mean that the Mesoamerican horses would be pretty inbred, as other posters have stated.
Peter Michell's "Horse Nations" is a good resource if you want to pursue this idea further.