Well I always ask the people who ask these questions this:
What type of gameplay interests you more?
Red Dead Redemption is an excellent Third Person Shooter Open World Game is great Story Telling elements along with great music and voiceacting, superb gameplay, tons of side quests and challenges, etc and it packs so much value and that's only the Single Player Part I'm talking about. Multiplayer is an absolute blast but you need friends to play because there's no matchmaking in RDR.
Medal of Honor on the other hand is a FPS Game set in a Modern Timeframe. I can't give you much insight as to how great Medal of Honor is but from what I've been hearing, the Single Player Part of MOH is very good. What you can do is I think there's a MOH Multiplayer Demo releasing this week on the PSN and you can DL that and see whether you like the Multiplayer of MOH. The purpose of this demo is to show the players what's been improved since the Beta.
Yes MOH will have Killstreaks but don't think it has perks. Not too sure on that but think of MOH's Multiplayer as MW2 meets Bad Company 2.