After seeing "Smoke Signals" I went looking for other movies with Gary Farmer in them and found "Powwow Highway" from 1989. Not quite as good as "Smoke Signals" but still a worth watching. Ebert called Farmers's portrayal of Philbert "one of the most wholly convincing I've seen". Sherman Alexie wrote in one of his short stories that the highest form of literature for modern natives is the road movie and after seeing these two I say "ain't nothing wrong with that".
Further up thread someone recommended "In the Electric Mist" and I recently watched that. It's based on the novel "In the Electric Mist with Confederate Dead" by James Lee Burke, one of our finer, more poetic mystery writers. Tommy Lee Jones does a more than credible job of bringing Burke's rough-edged, flawed detective Dave Robicheaux to the screen. One of the highlights of the film for me was this haunting song that played over the closing credits.