The reason they sound different to you is because they're taking the same chord structure and putting a different melody on top. If you listen behind what Gotye is singing in the chorus to what the bass and guitar are doing, you'll hear that it's exactly the same progression as Rolling In The Deep, only played a bit faster.
And this is the issue. If you listen to music only for the singing, then you'll never notice. But if you listen to the whole song, rhythm section included, then you start to see the same progressions appear all the time. Someone already posted the Axis Of Awesome video that shows how many pop songs of the last 40 years you can play over the same four chord structure.
Imagine if games all followed the same fundamental structure. Instead of a focus on a variety of gameplay styles and genres, and trying to find new ways to play games, we had a homogeneous pile of games that only ever copied what has already gone before. We're already starting to see that with the relentless focus on military shooters all treading the same ground. Imagine if that wasn't just a brief trend in the industry, but the norm for 30+ years. Would get pretty tedious, wouldn't it?
By supporting musicians who try new things and are willing to challenge their listeners, not just with clever lyrics, but with interesting song structures and real musicianship. Bands like Porcupine Tree, Tool, Karnivool, Opeth, etc.
