This is my first Alternate History, so I might get things wrong, or out of order.
This POD is sort of two PODs (is that possible to have more than 1?) -
1 - A brilliant and wealthy Viking engineer/merchant has a dream of building a powerful colony in Vinland, and wagers his inheritence (risking everything) on 100 German horses (he purchases them as foals, since they're more manageable on a Viking transport ship), and 80 sheep. He intends to establish two colonies.
(I was thinking of just horses, but decided to toss sheep in to see how it might affect things).
2 - A storm near blows the ships off course (pushing them further south) to Newfoundland, near Maine. Thinking that it is Vinland, or some other northern land, they settle both colonies about 25 miles apart from each other, each with 50 horses, 80 sheep, and roughly 200-250 colonists each. (I don't know if this is too small or large of a total population).
The colonies are established in 1000 AD. Explorations parties travel on horseback, and meet several mainland tribes, most of which are hunter-gatherers, but some are semi-permenant (have villages in the summer). Local indian tribes now have some knowledge of these strange animals.
One fall, a powerful storm rolls in, letting the majority of horses and sheep escape. They make their way to some semi-permenant villages, and the villagers, having already learned of horses and sheep from the Vikings, keep a group of them as gifts to their village elder. These animals become a symbol of wealth, and are gradually traded south. By 1060AD, the Vikings have left the area, but not before horses and sheep begin to make their way southward.
I'm not an expert on horse and sheep population growth (I know a horse has 1 foal per year, between the ages of maybe 4-20 years old). But, if bred, I'm guessing that the horse population would be this:
1000AD - 100 horses.
1100AD - Over 700 horses. By this time, they would be trickling down the Newfoundland coast, into Maine.
1200AD - Over 5,000 horses. By now, they're a symbol of wealth across the extreme northern New England region, spread out over thousands of tribes. Horses are mainly used for scouting locations of prey. Sheep are much more numerous (1-3 lambs ever 6 months, I think -- is it possible to have 2-6 per year?), which allow tribes to remain in one area longer.
1300AD - Corn starts to reach southern New England. The Aztecs are starting to build their empire. There are now close to 40,000 horses, and they're all over the northeast US, and eastern Canada. There still aren't enough to actually be used in armies, but enough that tribe chiefs can have a small herd. Sheep are much more numerous, being traded along the Great Lakes, and east coast.
1400AD - The north east cultures have a viable system for permenant settlement. Corn in the summer (plus beans and squash), and meat (sheep, maybe horses) in the winter, as well as wool clothing. There's well over 250,000 horses now (Yes, I'm estimating the horse population by assuming a 2% growth rate - I know it isn't scientific.), with a range from the Mississippi to the east coast.
Corn farming, plus horses and sheep, I think would have helped cultures grow better, and have much more influence. Perhaps the Iroquois, having horses before the Huron tribe, could have conquered them before the introduction of Gunpowder by the Dutch. There's probably enough horses in some cultures for small cavalry-based armies. The tribes of the plains would be raiding Mississippi cultures for their horses. Being archers, this would be a boon to these tribes in their raids.
1450AD - About 750,000 horses (assuming predation isn't a problem, and horses haven't been killed in wars, etc. It's probably more like 500,000.), and probably more than enough sheep. Populations are growing quite well in Eastern America and Canada. Tribes from the plains are probably also raiding into Mexico, playing havoc with the Aztecs, and other cultures.
1500AD - Horses make their way down to Panama, and now play an important role in Mesoamerican empires.
1519AD - Cortez finds a much different Mesoamerica than our timeline. Perhaps the Tarascans, who had early bronze weapons (not the best, but they could break obsidian) might have conquered the Aztecs. Maybe there could've been a mixture of cavalry, bronze-age military, and archers that resembled the technology level of the early Babylonians or Egyptians (without the chariots). Still not a match for 1500AD warfare, but at least they would have some resistence to European diseases. South America would be just starting to see horses and sheep, but it wouldn't help them, especially with Panama being something of a bottleneck - not many horses would be able to get through - at least not without trade.
North America might've resembled "old world technology" between 1500BC-1000BC, when cavalry were starting to be used more by many European and Middle Eastern cultures, but without bronze and iron - provided knowledge of bronze hasn't been traded yet. Granted, it would take another 1,000 years for it to fully develop.
With gunpowder in the 1600s, northeast tribes would have had a 150-200 year head start on gunpowder cavalry before European colonies became organized enough to start invading. Tactics such as giving the Indians disease infested blankets wouldn't have been as effective, as diseases from domesticated sheep and horses were already around for a few hundred years. That tactic might be more effective out west, though.
One thing I didn't take into consideration is how trade would affect things, such as technology. Granted, by the time horses get down to Mexico, it would be a bit too late, with the Spanish conquering everyone. Although, if any of the tribes had worked on their military tactics for the past 100 years, it might not be as easy for 600 troops to face down tens of thousands of swiftly moving enemy troops.
While it wouldn't have helped much, it may have helped determine who was able to colonize which part of North America. For example, maybe the Dutch have greater range of the east coast, since they have Iroquoian (or whoever is dominant) musket cavalry fend off England, Spain, France, and others.