The restaurant in the Monument Valley visitor’s center on the Navajo Nation serves Navajo food - and not just fry bread tacos, but lots of meat dishes and soups. I remember it being very good.
While restaurants exist, I think you’d be better served going to a powwow or other festival.
It doesn’t exist any more, but there used to be a Yah - Ta- Hey Navaho Taco place at Trolley Square in Salt Lake City. Trolley’s been considerably shaken up since I left, ages ago, and almost everything is different, so I’;m not surprised that it’s gone from there. A quick internet search shows it hasn’t relocated elsewhere in the city, though. There are other Navaho restaurants, though, there and elsewhere. I see there’s a Navajo Hogan on 33rd South:
http://www.urbanspoon.com/r/54/591483/restaurant/South-Salt-Lake/Navajo-Hogan-Salt-Lake-City
There used to be a restaurant (now defunct, I believe) in Cherokee, NC that sold “Native American” cuisine. Apparently, according to my Cherokee friends, it wasn’t authentic and it was priced for tourists. I did eat rattlesnake there once, but my guess is that rattlesnake is not a common staple for the Cherokee.
Very good, in my opinion. My husband could happily live off that menu but for one thing- the Rez is dry.
I, on the other hand, could live off the fry bread alone.
There was a Bison meat place in Ruston WA (never went in - that stuff is like biting into a blood clot for me), and, over along Hood Canal on the reservation, places with fry bread w/ honey butter. Not as nasty as a Krispy Kreme, and just as good as New Orleans beignet.
My wife and went to diner in Cherokee that had a Native American buffet night with stuff like rabbit, buffalo, trout and other items native to the Americas. Have no idea how authentically Cherokee that stuff is though.
In fact the Seneca Casino restaurant was called The Three Sisters, the name they gave to corn, beans, and squash, the staples of their diet. It still is, but the menu is basically identical to Chili’s or Applebees.
They easily could have updated the dishes to modern tastes. Nobody really expects any other type of restaurant to feature recipes unchanged from peasant days. Modern corn, beans, and squash have been subject to 500 years of cultivation anyway. I bet a pre-contact Seneca would hardly recognize the taste.
We’re deeply into a period where spices are the rage, but that’s something brand new in my adult lifetime. German restaurants were once common, and even upscale, and their cuisine is hardly spicy. English-style pubs are everywhere and English food is notoriously bland - they go to Indian restaurants when they want spices. Cuisines that feature spicy foods, like Mexican and Asian, were literally unknown when I was growing up. Chinese restaurants were Cantonese, filled with dishes that were basically bland American, like chop suey.
What we think of as American food is itself pretty bland. Blandness has always sold well in America. Think of a classic Thanksgiving dinner. It’s not only bland but entirely in shades of beige. 
(And a modern-day turkey looks and tastes nothing like a wild turkey of that era.)
I would explain the presence or lack of certain ethnic cuisines culturally by the size of the immigrant population and the tendency of that population to start restaurants. It wasn’t that lots of Scandinavians opened restaurants but saw them fail because nobody liked the food. They simply didn’t open restaurants. I don’t know why but I’m sure some sociologists have studied it.
The restaurant at the Crazy Horse Monument in South Dakota specializes in Native food. Here’s a link to their Laughing Water Restaurant; they show stew and tacos, but they also have bison burgers etc.
\Tangent A great article recently on Scandanavian foo - with recipes I intend to make over the holidays: New Nordic Is Cool, But Old Scandinavian Food Holds Its Own : NPR (Anybody know where I can find enough rose hips?)
/tangent
My Thanksgiving dressing recipe is supposedly Potomac in origin. Corn meal pre-roasted and then combined with game broth, oysters, slow-roasted ramps if you can get’em, leeks and elephant garlic if you can’t, and wild parsley and/or dandelion greens. Mmmmmm-mmm! Don’t know if those ingredients ever really made it to one geographic area though. Ramps grow in the high hills, oysters not so much. . .
My wife and I ate at a restaurant in Cherokee three or four years ago that advertised native American cuisine. I got an Indian taco–fry bread with beans, cheese, and meat. It was one of the five worst restaurant meals I’ve ever eaten, as if the cook was actively malicious toward diners.
There used to be a restaurant in Asheville called Spirits on the River that served a variety of wild meats, native-American style. I was a pescatarian at the time, so my options were limited, but I heard other folks say it was quite good.
Five years or so ago we ate at a restaurant on a Navajo reservation near the Grand Canyon. I got a Navajo taco there, and it was middling–not great, but okay. I can see how if it were done well it’d be delicious, this one just wasn’t done all that well.
And then some twenty years ago I ate at the Pueblo Cultural Center in NM (Albequerque, maybe?). I got a bean burrito. You gotta understand, I love me some bean burritos, I eat at least one every week, they’re one of my favorite foods. This was the best goddamned bean burrito I’ve ever eaten in my life–decades later, I still tear up at the memory of its deliciousness.
I spend a lot of time in Oakland, and I have to tell you, what I call The Oakland Oak (it’s an oak tree right next to City Hall) produces some fat, luscious-looking acorns. I mean, you know, from a healthy-looking-fat-nutmeat perspective.
I have always wanted to try acorn bread, but I understand you have to leave the shelled acorns in a running stream for a week, to get the tannins out. Maybe there’s another way?
Would Indian Fry Bread be of Navaho origin?
What about the pre-reservation Sioux, like in Dances with Wolves, would they have eaten Fry Bread?
I wouldn’t exactly call that authentic. Not a lot of salmon in South Dakota and I doubt the Sioux of old were making bison burgers. Not to mention, you can get bison burgers pretty much anywhere in western South Dakota.
Still plenty of bison around. As a matter of fact, there is an annual auction in Custer State Park in South Dakota to thin the herd.
You can get local bison from Upstate New York. Of course, you can also get local ostrich. Local doesn’t mean what it used to.
I always thought it was a relatively modern invention (i.e. last 150 years or so.) It’s made from wheat flour after all.
Well, we put corn syrup in everything nowadays. Maize is quintessentially Native American.