I liked John a lot, but Red wins any day. It might be cliche, but isn't that what we wanted? If you don't want a cliche western, go play samurai western or whatever it's called. If a character like Red doesn't come up when you think of a true, spaghetti western, then you haven't been watching the right movies.
You must mean such classics as Shane, Butch Cassidy & The Sundance Kid, The Shootist, Fistful of Dynamite, Once Upon a Time in the West or The Wild Bunch with their similarly ambiguous/downbeat/bittersweet endings? No, man - RDR's ending was beautiful. Not just one of the great game endings, either; it was one of the great WESTERN endings.
Redemption is, however, easily as cliched as Revolver, in my humble opinion. You have a point about Revolver, though: it is very much a Spaghetti Western thing. Christ Alive - it directly quotes the opening to Django!
Red is a prototype at best and two dimensional characters of his ilk are two-a-penny. They've been done far better elsewhere, namely in the films these games homage. John's a far deeper and rounded character who is more of a badass for it. Red's whole character is but an aspect of John's.