Victor Mature and Anthony Quinn were both actors who at various times in their careers played Native Americans in the movies. In the 1955 movie Chief Crazy Horse, for example, Victor Mature played the eponymous Lakota Sioux war chief, Crazy Horse, and in 1936 Anthony Quinn played a Native American in the movie The Plainsman.
In Thomas King's "A Seat in the Garden," Red thinks that the Native American in Joe's garden looks a little like the two aforementioned actors. The point the author is trying to make here is that when many people see Native Americans they see a character from a movie. Often these characters are reductive stereotypes, and thus people's perceptions of Native Americans are misguided and ignorant. Indeed, it was because of these reductive stereotypical portrayals of Native Americans in Hollywood movies (as well as similarly reductive portrayals of other minority groups) that Marlon Brando, in 1973, refused to accept an Oscar for his role in The Godfather.
In King's story, Red also believes "with all his heart that he had met this Indian before." The author here is emphasizing the same point. Red believes that he has seen this Native American before because he has seen Native Americans portrayed so many times in the movies. The implication of Red's wholehearted belief that he has seen this Native American before is that it is easy to mistake one Native American for any other when the portrayal of Native Americans in the movies is so homogenous and so reductive.