I too would recommend Bromanov's approach. Stick with the rules as much as you can. And don't be afraid to make encounters brutally difficult, because that's where the adventure really shines. But you can also take this mechanic and open it up to a different playstyle:
For extra flavour; in the Medusa's example: if all players avert their eyes, You could just take the Medusa off the board and keep a personal map on where she is. Then make the players "guess" where she is, e.g. using perception (hearing) on where the Medusa might be. This might make for a fresh approach to the encounter, thus make it more of a tense game of hide and seek. That way you also make it more like a roleplaying adventure and less like a tabletop version of a videogame.
But it does raise a legitimate question which we should further explore:
How would, say a "Fireball" spell or "Lightning Bolt" spell work with "Averted (or shut) Eyes"? We might be in different minds on this. Say a ranger is 70 ft away from the Medusa and thus avoids the Gaze-effect. The ranger knows where the medusa is. A wizard who was a bit careless, is suddenly "up close" at 15ft from the Medusa. The wizard says "I avert my eyes", so he shouldn't know where the Medusa is.
Now here's the rub. He doesn't exactly know where she is, But on the Wizard's turn, he says "I'll throw a fireball that hits spot X, thereby taking only the Medusa in the AOE... but how would he know? And how would he (blindly) know how to hit spot X?
I have a wizard in my group who would say "I just throw it at a spot... uh... here..." -the spot being the perfect spot to both hit the Medusa and avoid friendly fire. But how would he look at the spot, whilst avoiding the Gaze? (And having the ranger say "oh, but I cry out where she is" seems like a very cheap encounter mechanic.) Though it could (maybe) be slotted into a "Help" action?
So when dealing with said problem, I give the Medusa advantage on the saving throw, and even make the player roll a DEX-DC to make sure he/she hits the intended spot. Thus mimicking the player's squinting eyes and averted gaze. The idea being that "you should compare it to trying to bolt/nail something to a wall or draw/write something with your eyes averted". It seemed the fairest approach to me... but I guess that's personal flavour. For me, "averted eyes" is supposed to generate tension, even frustrate the players somewhat.