I recommend just not buying any game at full price. Every game is discounted at least 20% at some point shortly after release, and games that don't sell well can usually be had for 60% off or more a couple of months later. That's plenty of time to find out through the grapevine whether it's a bargain gem or still not worth a buy.
This is what I do. For all but those few games that I just know I must have on day one, I wait it out. For me, top tier (to me) games that I don't need instantly are purchases at $35-40, and any others (the vast majority) I wait until they are $20 or less. It means I have to wait, but that's fine. It also means I have time to hear opinions on it. Plus, with the backlog of games I already have (and have bought cheap) I have no shortage of things to play.
I never beat games quickly enough to have trade-ins work for me, and I don't play regularly enough to have GameFly work for me necessarily, so this is how I've done it for quite a while now. It means I can amass a collection for relatively cheap, and play the games whenever I have time. GameFly might work out to be cheaper overall, but only if you can play regularly. For me, sometimes I can play through 3 games a month, and other times it'll be 2-3 months to finish a game.
Just my 0.02
EDIT: To comment on the original RedBox post though, I really like the idea. There are a decent number of games that I'd love to try over a weekend for $6 and be done with it. DNF springs to mind, but there are others. In those cases, it'd take ages to wait until that game drops to $6, so I'd definitely use RedBox. I haven't used them yet, but definitely would.