I've been to the Hopi Cultural Center restaurant on the Hopi reservation in AZ. If I remember correctly, all of the main courses on the traditional part of the menu contained some sort of meat, but I think everything would probably be relatively easy to veganize. I do remember eating
this ("Spread on hot, greased griddle or stone with palm of hand"), and I bet the other recipes on that site are pretty adaptable.
Navajo Tacos (recipe decidedly not vegan)have always appealed to me, but I've never had one.