This question is too big to really answer, not only because of the localized variance in the exercise of citizenship rights by indigenous people, and the push and pull thereof throughout time, but because semantically “citizenship” is a difficult term to pin down (i.e. state, tribal, or federal, and de facto or de jure). I hope others can chime in with other cases. I’ll offer the example of Eastern Cherokees. Now, in your question, you point to 1866 as the beginning of citizenship for African Americans. This is problematic for a few reasons: one, because obviously well into the 20th century, there was widespread denial of African Americans’ citizenship rights; two, because some African Americans did exercise these rights much earlier (for example, free people of color in NC technically had the right to vote prior to 1835). The same sort of quandaries existed with native peoples: they may have nominal citizenship based on legislation, but were deprived of the actual exercise of citizenship rights on local levels for many decades after. Voting rights are often considered the “final frontier” here. And, just as military service of African Americans was one way that the question of citizenship rights could be pushed to the forefront of the national debate, the same was a consistent theme with Eastern Cherokees and other native groups. It’s a question that echoes through centuries of American history: why should I risk my life for my country if my country denies that I’m worthy of true inclusion? Some Eastern Cherokees had nominal citizenship since treaties of 1817 and 1819; provision was made partly because of their “loyalty” to the US in serving in the Creek War a couple of years earlier. But those who took this “citizenship” had to essentially renounce their allegiance to the Cherokee Nation, and while they were expected to be accountable to the laws of the state where they resided, they were not treated as actual “citizens.” It was a huge dilemma for them to either retain traditional lifeways and social organization, or conform/“acculturate” to the standards mandated by US Indian policy. Most Eastern Cherokees straddled this line with “syncretism”; i.e. retaining traditional language and cultural practices in their communities while adapting to be considered “civilized” as they sent delegates to Raleigh and Washington to further their claims. They were protected from removal and could own land (but this became a very tricky issue for their heirs). They remained in limbo— in the “anomalous status” identified by John Finger. In some instances, they could be murdered and robbed with relative impunity; their testimony was thrown out in the courtroom; their future and that of their children was always uncertain as the federal government continued efforts to remove them into the late 19th century. Junaluska— who was removed on the “Trail of Tears” but later returned to NC, whereupon he was explicitly granted state citizenship due to his heroism in the Creek War— provided an early precedent of the exercise of citizenship rights. But the rights respected with one individual did not mean citizenship for all. Many Eastern Cherokees served NC in the Civil War. The Confederacy implicitly accepted their citizenship to an extent (and famously gave representative power to the Cherokee Nation). After the war, for Eastern Cherokees, their right to remain and to own land was explicitly upheld; this was still not true citizenship. The 14th amendment (with “excluding Indians not taxed”) did not guarantee citizenship to indigenous people, again due to the complications of what this meant on tribal, local, state, and federal levels. It would take subsequent generations of sacrifice in the world wars, and the persistence of Eastern Cherokee activists who were denied their right to register & vote, for the idea of their genuine citizenship to have enough popular appeal and backing. In a nutshell, native people did assert their rights early on, but it took much longer for these rights to be guaranteed— and even today many Indian people would attest that they are still held back by centuries of not only dispossession by the US but exclusion from the US.

See John Finger: Eastern Band of Cherokees, 1819-1900 & Cherokee Americans