I watched Unforgiven in preparation for your guys' discussion and I thought I'd share my thoughts on the ending (as it relates to the film's drastic tonal change).
If Unforgiven was a conflict of redemption v. regression inside Munny, we probably wouldn't have even seen a lot of the Lil' Bill story. It wouldn't have been necessary, so the inclusion of Bill and his arc is ulterior. Bill begins to write a heroic narrative for himself through the Beauchamp character; he even makes sure Beauchamp is paying attention, "taking note" of anything "heroic" he does. I think Adam also suggested the house Bill was building may have been a representation of his humble/artisinal narrative. In his story, Munny is a villain. The first time Bill meets Munny, he vilifies him as "trash" without much insight, and brutalizes him in the same way he did English Bob. The end to Bill's narrative, of a good man only trying to make peace, is a fight with a real monster, the monster William inadvertantly became.
The ending was appropriate because it was exactly how these two men imagined their stories would end (except, I'd think, Bill assumed he would be victorious and William assumed he would die). I'm sure there are also valid theories of the ending being a social regression, but that seems more like an Andersonian method, and i don't think Eastwood was really trying to make much social commentary (at least, i don't think there is enough solid evidence to suggest he was). I think that Eastwood was trying to evoke the way moments of legend are idealized, or as they would be by the participants in the story. The first 4/5ths of the movie are about characters separating themselves from these kinds of legends, but the ending was the indulgence therein, where these characters ultimately feel they belong.