I made a map with the major river systems and threw in some ideas of how the continent will be laid out, I assume it's not very much like what you were thinking. I can change anything on the map pretty easily so just tell me what to put where. It's just vague areas circled for different groups right now, as it gets more fleshed out I can change locations of things and refine it with more detail, province divisions, names of cities, regions, etc.
http://kupax.com/files/15003_dvp8u/ideas.gif
Nice map! But I think those boundaries are a bit too wide.
If it's to be a medieval scenario, then the European settlers need to behave like medieval people. For one thing, they won't have much in the way of transoceanic trade - so fur hunting is right out as a means of making a living. The Canadian interior and Labrador will remain unsettled, and the great lakes region is not a very inviting place either. Nothing like the early French exploration would happen.
Secondly, since people have only access to not very seaworthy ships, and are not naval-oriented by natural disposition (excpetion: Vikings), settlements along a coast are difficult to maintain for economical and military reasons. Rather than extending their settlements along the coasts, they would bunch together, and try to carve out a territory of their own towards the interior, a fiefdom with as short borders as possible. Think County of Edessa. Coasts with difficult terrain right behind them are downright inhospitable - shallow settlements along the coasts of, say, South Carolina, Florida or Alabama would not be able to defend themselves against the hostile Indians of the swamplands behind the coast. The fertile interior of New York, Delaware, New England or Maryland on the other hand would be a good place where the "core" of a medieval society could develop, there's ample room, the terrain is not too difficult, the soils is fertile, and you can shove out the Indians by pushing up the rivers and linking the settlements.
Then there's the psychological element. Medieval peasants are not supposed to be adventurous people. They shy from wild, dark forests with strange peoples whose behavior towards arrogant strangers could be right out of a scary nightmare. They will wait for their dukes and princes to conquer these lands from the natives in the name of God, and then follow those lords as they establish new fiefdoms and invite settlers. So unless you make the Indians all disappear from diseases (where's the fun in that??), this would mean, waves of settlements would only follow those big "crusades" against the heathen forest and swamp dwellers. Those campaigns would be big endeavours, not small-scale frontier warfare. Think baltic crusades - they're crusades whose movement you can put on a map with big arrows. As often as not, a crusade may fail, with lots of lords and their knights ending up slaughtered in the wild forests, their skalps and armor ending up as decoration of some supreme iroquis chieftain's main hall.
Lastly, economics again. A medieval economy is an economy without much specialization. Farmers don't produce much in the way of cash crops, rather they produce food, and surpluses are small. Therefore there are few cities. The centers of medieval civilization (in the classical, western European sense) are the courts of the kings, who often or not may be travelling courts, or courts that convene only every now and then, since the appetite of the king's entourage would quickly exhaust the stores of the local towns, if they made their court permanent. The dukes and barons would most of the time be in their own lands. This means that, for a kingdom to expand its power, it needs to expand its territory, more precisely, it needs to expand the size of its arable lands. Conquering "strategic" islands or coastal fortresses is not going to happen, since a territory can only be held permanently if its inhabitants and the garrison can live off that land. No settlement in Florida or on those small, sugar-growing caribbean islands.
I felt so bold as to take your map and paint the areas on the continent that I think would make good areas for medievals at game start:
The "Marshland Indians" area is pretty harsh for medieval settlers, for reasons I outlined. Same with the Great Lakes area. Both could be areas where Indians resist the Europeans.
The light blue area I took to be Vikings of some sort. They could have fun raiding the dark blue Europeans in the east coast area for easy loot, and otherwise make a living fishing and a bit of farming.
Now in the dynamics of the game, the blue east coasters would probably seek to push towards the Great Lakes, towards upstate New York and towards Kentucky across the Cumberland Gap, since those are the areas where fertile land is to be had. They'd also probably fill up Maine and northeastern New England as well, but without so much fuss as big crusades.
The Vikings would push up the St Lawrence river in quest for land, as well as what's southern Ontario nowadays, and would raid the east coast. Going towards Labrador or the Canadian interior to their northwest would not be so inviting, it's cold, densely forested and full of hostile natives. They would clash with the East Coasters in upstate new york eventually.
The purples, which you labeled as Arians (?) could bunch their settlements around the most defensible area, i.e. southern Louisiana, and expand inwards from there. I don't think they would settle the Alabama coast or the Texan coasts, for lack of defensible lands, and for other reasons outlined above. Their expansion dynamics would lead them up the main rivers, towards the fertile lands of Arkansas and eventually Missouri. They could also push a bit towards western Georgia, but AFAIK that was mostly swamps before European settlement? Might not be as inviting as the more open land along the mississippi.