I felt like Naxx had the right level of power, with a few exceptions. GvG isn't really too strong for the most part, it just has a lot of RNG crap. LoE and BRM are solid. It's really TGT that is a piece of crap set, and this set feels more like TGT than everything else so far.
TGT cards are bad specifically against the over-powerful Naxx and GvG cards - not against the base or classic sets. I don't feel like your view on either of those sets is colored by actual experience with the changing meta, as you only started playing recently.
Naxx started the trend of sticky, deathrattle minions that are undercosted for their abilities - nerfing removal and AOE and enabling a two-year long aggro meta. GvG only bolstered the tempo game, and seriously hurt the card variety, by releasing cards like Shredder and Boom - which not only fit into every deck archetype, but are almost unilaterally the best cards at their mana cost in any deck.
Essentially, the cards in GvG were either undercosted or had too many stats - were too sticky and proactive and fit into too many archetypes. RNG is actually not even a top-3 reason that set is broken IMO.