Whilst I would be very against the outright banning or neutering of a "specific" hero, either for offense or defense (referring to the Medusa reference for example); I am all for severely impacting them (and others) in some more general manner like having a "dumb & dumber" debuff that would negate 30% expertise on the attacking team. This would reduce Medusa's overcharge and ability to stone, likewise Dragon Slayer Banner size etc and would create challenge.
I strongly support the idea of "element" themed buffs like fire, water, healing, toxic, holy etc. But make them meaningful, so 200% health, 20% energy, 30% damage etc. None of this 10% garbage, that's meaningless. What would be even better (better even than the current fire boost of just flat 200%) would be to scale it per hero in team. So +50% fire damage for each fire element hero used in team. That would lead to variety and challenge in teams and could still be applied to both attackers and defenders rather than purely one sided.
I would also like to see more modifiers based around fundamental stats like Intellect, Strength and Agility, as well as others such as Shields, Tenacity, Dodge, Accuracy, Movement Speed, Crit Rating, etc. These could have interesting interplay and create interesting challenges.
Finally, introducing temple Titan like buffs, but maybe more creative, so we could have random Minions being dropped into battle on the defenders side, or a lightning blast from the heavens, or a cold stone wash across the battlefield, an energy vortex that periodically plays havoc... There are so many possibilities here.