If you like the idea of a western themed game with gunfights being the main focus, then you'll like either of them. They're both pretty short though.
I'd say that Red Dead is more `arcadey' than Gun, which is a much more open-ended, run around and pick your next mission sort of game. I liked the soundtrack and atomosphere of Red Dead better, along with the fact that you can play as multiple characters.
In any case, I played the Xbox versions of both. For Gun it dosen't seem to matter much which one you get, but for Red Dead I'd get the Xbox version. Here's a quote from the Gamespot review:
"Between the Xbox and PlayStation 2 versions of Red Dead Revolver, the Xbox version is far and away more visually appealing. The frame rate is higher and more consistent, textures are cleaner, lines are less jaggy, and the various special effects employed by the game just look better."