Fry Bread really isn't native american food, for that matter neither are Indian Tacos. Fry bread came about as a result of the supplies given to the native american peoples in the 1800's who were relocated to reservations, these supplies consisted of flour, lard, salt, and some sugar, which resulted in what we know today as fry bread. It was a poor nutritional substitute for what the people were used to eating, but it was filling.
As for Indian tacos, not many tribes had, tomatoes, garlic, onions,cheese, salsa, lettuce, hamburger, etc. any or all of which one might find on and "INDIAN TACO".
To find real native foods,try pemmican, bison, venison, berries, hares, ground animals, pine nuts, maize, etc. or as others have stated the foods on the northeast and northwest coasts will be your most authentic, as will be the foods of the real Seminoles. It is important to remember that many of the plains native americans, and other tribal members from the interior of the United States were moved to differeent parts of the countrty. One of the reasons was to isolate them, and another reason was to move them out of areas in which they were familiar, and into areas that would not sustain them in thy way to which they were accustomed