Kochman; admirable response, and I'll endeavor to do so.
The first general source that springs to mind is the Cambridge Atlas of World History, p. 25. The Adena and Hopewell cultures were the earliest farming societies and by "2500-2000 BC" had developed "long-distance trade networks" and maize cultivation, an agriculture that allowed substantial demographic expansion. The mounds that appear throughout the Mississippi river watershed area are ubiquitous, still visible, and most have been excavated, demonstrated a population dense enough to be mobilized for large-scale building projects. In the same publication, p. 109, the relevant map show no less than 5 widespread cultures in the watershed area, each w/at least 10 cities, the largest, central region containing in excess of 50 cities. "Mounds in the heart of these centres were crowned by temples and sometimes the houses of the elite." These are "ceremonial centres for their surrounding communities." The initial explorations of the southeastern regions were conducted by Spanish explorers, and De Soto is the primary examplar. De Soto visited, according to his reports, very many cities throughout what is now the US "deep south." By the time that La Salle explored these areas, the cities were gone.
Jared Diamond, author of "Guns, Germs, and Steel," in his subsequent publication, "Collapse; How Societies Choose to Fail or Succeed," in chapter 4, p. 136-156, "The Ancient Ones," detailed the rise and fall of the Chaco Canyon culture, a location I have visited. Pueblo Bonito is the Spanish name given the ruins, as the people who settled there had long since brought about their own collective demise via deforestation and resource depletion. The chapter details the demograpics throughout the period of settlement and the scientifically-discovered reasons for the collapse. Chaco was not only a city, but the cultural, political, and trade nexus for a number of smaller sites identified as "towns." Chaco is by no means unique to the region. The Mesa Verde national park is not that far away in southwestern Colorado, I've visited there too, and these habitations are clearly cities.
Orellana, a spanish explorer of the Amazon River basin in the 16th century, reported that there were large cities along the river, right up to the mouth. Subsequent Spanish and Portugeuse explorers failed to find these cities and Orellana was discredited. The truth of these cities has only recently been established by means of soil analysis. The inhabitants of these cities had a knack for enriching the jungle soils on a apparently permanent basis, a skill which, to this day, cannot be replicated, and the sites were first located by noting that farms and farmers working the Amazon basin today still travel to the ancient city sites (not knowing what or why), in order to collect a soil type that is substantially more productive than surrounding soils. Satellite analysis subsequently revealed that these soil sites exist throughout the river basin and each is the site of a city--excavations proceed.
If you'd like more examples, I can provide them. Hopefully, these exemplify the city-based cultures that existed prior to the Columbian Exchange. About the plains Indians; before the 16th century, these groups were hunter gatherers, and had been marginalized by groups farther east--the French name, "Sioux," was derived from a term that translates as "dog eaters." It was only with the arrival of the Spanish, and the reintroduction of the horse, that these groups flourished and expanded their influence, probably the only example of a Native American group that gained positive benefits from the Exchange. Even these groups were struck by Virgin Soil Epidemics, however, with the example of the Mandan, almost wiped out, by smallpox in the mid-19th century.