And there were certainly plenty of empires in Mesoamerica and South America, and some widespread civilizations and trading communities in North America, so that wouldn't have to be entirely fictionalized. Maybe the quest narrative could be something along the lines of a member of a small migratory Algonquian community traveling to a place like Cahokia and eventually joining a quest south to a great Mesoamerican kingdom, sort of like how the hobbits in LOTR travel from the Shire toward more central, more powerful civilizations.
That's along the lines of what I was thinking, though my greatest familiarity is with the Mississippian culture of which Cahokia was the prime example. There's good evidence that this culture traded with Mesoamerican cultures as well as with far flung groups in today's Utah, Idaho and New England. The part that would have to be fictionalized is that most of the most noticeable expressions of cultural power (i.e. big cities and wide-spread cultural complexes) did not happen concurrently. The Ohio Hopewell culture, which built the effigy mounds such as Serpent Mound, was around 200 years before Teotihuacan was at its height, which was 400 years before Cahokia which was at its height 400 years earlier than Tenochtitlan. So, it's at that point that you have to start inventing Rohan, Gondor and Mordor, if you know what I mean.