Petrification is one of several iconic save-or-die effects that have persisted throughout many Dungeons & Dragons editions, whether forcing a save versus petrification or making a Fortitude save, your survival boiled down to a single die roll.
One of 4th Edition's controversial changes was reducing the immediate impact of save-or-die effects: if you got his with a medusa's gaze attack and it beat your Fortitude defense, you would be initially slowed. On subsequent rounds you got to make more saving throws, with additional failures immobilizing you, then finally turning you to stone after strike three.
I liked this because I felt that it added more tension to the game, especially if you or other characters had access to powers that granted saving throw bonuses. I also liked that some monsters had ways to restore a petrified character, such as by creating a poultice from a cockatrice's feathers and blood. To me this helped mitigate the former game-stopping impact of a few bad rolls, which would have been nice in 3rd Edition, where a party of seven was wiped out in the first random encounter against a pair of cockatrices.
I like the idea of basilisks as an ambush predator, as it helps separate them from the rest of the petrifying participants. I kind of wish that they would have borrowed the bit about how the mythological basilisk's presence could kill plant-life and crack stone. This could make for good foreshadowing, as well as an adventure hook where one or more basilisk's are intruding into a region and gradually destroying it. I also liked a lot of the 4th Edition variants, such as the venom-eye.
Though small, these guys come in flocks and can fly, which already contrasts greatly against the largely solitary basilisk, gorgon, and medusa, but they also have a fairly unique petrifying bite attack. I really have no complaints about them, though I never did understand why they could see ethereal creatures. I guess being able to stun ethereal creatures is different.
Large size, a petrifying breath weapon, and presumably some kind of goring attack gave been the gorgon's staples throughout the editions, and I have no real complaints about them now. The gorgon sets itself apart by being much more durable than the cockatrice, more mobile than the basilisk, and having an area-affect breath weapon, so you cannot simply avert your eyes or rely on heavy armor to keep it at bay.
As with the cockatrice, I am confused by their ability to see ethereal creatures, as well as their ability to turn them to stone, and as with the basilisk I hope that they throw some variant gorgons at us, too.
Up until now I had no real problems with any of the monsters, but I have no idea why, in a game where the gorgon is a metallic bull instead of a trio of snake-haired sisters, and the basilisk is an multi-legged, lizard-like beast instead of a snake, that they want to stick with the medusa--which was the name of one of the aforementioned gorgons--as a unique creature.
Personally I think that if a DM wants a medusa to be a unique creature, that it is easier to increase its overall power, than to potentially have to decrease it in order to accommodate a race of medusas. One of the Planescape monster books had some legendary monster entry, and I recall a few templates in 3rd Edition that let you really ramp up a monster's power.
This means that the default medusa might gradually petrify her victims, while the "medusa of legend/paragon medusa" might have an instantaneous gaze. This could also extend to other monsters, giving us, among other things, a much tougher minotaur, hydra with no head-cap, and a lion that must either be strangled to death or cut with its own claws.
This does not mean that I think that they need to be a true-breeding race with maedars and all: they could still be the results of curses, spontaneously arise from the blood of other monsters, or created through dark rituals. I just think that the default assumption should be that there is more than one.