Well, I thought the Pueblo were the best choice, but I certainly don't expect them anymore. Of that list, Cherokee and Navajo are the best, but I'm not a fan of your list. Generally speaking, I want a sedentary civilization, not a nomadic or raider civilization, so I have strong objections to the Sioux, Apache, and Comanche (I'll grandfather in the Sioux because they appeared previously, though).
My other two options I'll suggest are these:
The Haida - Pacific Northwest culture. Brings in the Totem Pole aspect of Native American culture. They had an interesting combat style too (they were essentially the Vikings of the Northwest). Problem, we already have the Danes, so they might not want more Vikings
The Mississippians/Mound Builders - Undoubtedly the most complex (and believe it or not, influential) North American Indian civilization. It's possible to cheat a bit for a leader (Tuskaloosa was
a Mississippian leader, he just probably wasn't an important one).
ETA: Just beaten for the Haida
I'd love to make a new poll (with multichoice options) because I could probably put about 15-20 choices instead of 5.