"But his wife looked back from behind him,
and she became a pillar of salt."
– Genesis 19:26
The myths and stories are never very specific as to what type of stone victims were turned into, but I can envision a Hargravian petrification spell table that details all the different types of minerals the enterprising sorcerer could change his victim into.
With regard to monsters that possess the ability to petrify their victims by gaze or with a touch, there are three main mythological creatures that have all been used in D&D and other FRPGs. Note that details about these creatures vary with the story being told, and some interpretations are of modern invention.
A. The Gorgon was depicted by the ancient Greeks with serpents for hair, wings, boars tusks, scaly skin, and a protruding tongue. Its visage was so terrible to behold, that the sight of its face would turn the viewer to stone. Somewhere along the line, the Gorgon turned into a triad of sisters – Medusa, Stheno, and Euryale.
"Near them their sisters three, the Gorgons, winged;
With snakes for hair – hated of mortal man"
– Prometheus Bound
By the fifth century B.C., writers started becoming more sympathetic to the Gorgons, describing them as both beautiful and terrifying.
Gorgons today, are commonly referred to as Medusae, and are most often depicted as having snake-like bodies due to the influence of Ray Harryhausen's work in the 1981 version of Clash of the Titans. This form is more reminiscent of Echidna, another serpent bodied female who is also said to have been depicted with snakes for hair (though I have yet to see any such images). Another recent invention is the depiction of Medusa's petrifaction ability as originating from her gaze, but from what I understand of the myth, it was always the other way around. It was not being looked at, or meeting her gaze that turned the viewer to stone, but it was rather seeing her horrible visage that did this.
Anyway, just as Echidna was known as the Mother of All Monsters, Medusa was similarly the progenitor of Pegasus, Chrysaor, Amphisbaena, and the poisonous vipers of the Sahara Desert.
As far as miniatures go, both humanoid and serpentine forms of the Gorgon exist, though I don't think I've ever seen a winged version as depicted on Greek vases. The two humanoid Gorgons below are from the Ral Partha Female Creatures blister (Personalities and Things that go Bump in the Night 01-087), and the Grenadier Monsters of Mythology box set (Fantasy Lords 6004).
The next miniatures are a Mage Knight Gorgon (Pyramid #041), and two Ral Partha Gorgons (Crucible 91-506). The Mage Knight Gorgon had a severed head in her right hand, but I removed it as superfluous.
Two smaller serpentine versions are the Grenadier Medusa (Monster Manuscript Vol.VI 1506, MM49), and the Citadel Medusa (C18 Night Horrors).
B. The Basilisk was first described by Pliny as a small snake that seemed to be made up of one part horned viper, one part cobra, and three parts fantasy. The appearance of the Basilisk evolved over time, and has given rise to a number of creatures with the ability to either poison or petrify their victims.
"It is a native of the province of Cyrenaica, not more than 12 inches long, and adorned with a bright white marking on the head like a sort of diadem. It routs all snakes with its hiss, and does not move its body forward in manifold coils like other snakes but advancing with its middle raised high. It kills bushes not only by its touch but also by its breath, scorches up grass and bursts rocks. Its effect on other animals is disastrous: it is believed that once one was killed with a spear by a man on horseback and the infection rising through the spear killed not only the rider but also the horse. Yet to a creature so marvellous as this - indeed kings have often wished to see a specimen when safely dead - the venom of weasels is fatal: so fixed is the decree of nature that nothing shall be without its match. They throw the Basilisks into weasels' holes, which are easily known by the foulness of the ground, and the weasels kill them by their stench and die themselves at the same time, and nature's battle is accomplished."
– Natural History
Pliny's assertion that the Basilisk was a native of Cyrenaica is particularly interesting, because it is the location of the Libyan Sahara, where the drops of Medusa's blood were said to have spawned the poisonous vipers of that region. It could be interpreted from this, that the Basilisk is descended from Medusa.
The snake-form of the Basilisk is now largely ignored, and I propose using the term Asphynx (from SLASH'EM, a NetHack variant), or perhaps Ouraion (from the Hieroglyphica by Horapollo) to refer to snake-like creatures with the ability to petrify its victims.
The snake-form of the Basilisk was often portrayed with a crown on its head, demonstrating that there is a fine artistic tradition of illustrating monsters based on literal description that has been passed down from generation to generation.
Medieval sources describe the Basilisk as being hatched by a cockerel from the egg of a serpent or toad. Its glare had the ability to petrify a victim, and its breath was poisonous. This development lead to the next evolution of the Basilisk's appearance as a creature that was half rooster, half serpent. I would just call this particular creature a Cockatrice, and leave it at that.
For the final evolution of the Basilisk, we have to give credit to Ulisse Aldrovandi who provided an illustration of a Basilisk in his Monstrorum historia.
Aldrovandi's scaly eight-legged reptile ultimately gave rise to David Trampier's iconic Basilisk from the AD&D Monster Manual.
Two larger miniatures that can represent Greater Basilisks are the Grenadier Basilisk (Monster Manuscript Vol.I 1501, MM4), and the Reaper Basilisk (Dark Heaven Legends 02567).
For more standard sized Basilisks, there is the classic Grenadier Basilisk from the Denizens of the Swamp boxed set (AD&D 2010). Two different versions exist - one with a lifted foreleg, and the other resting on a rock. Next is a Heartbreaker Miniatures Thicket Basilisk (Magic: The Gathering 9135), and finally a Reaper baby basilisk from the Familiars II blister (Warlord 14087).
C. The Cockatrice was often mixed up in the Medieval mind with the Basilisk. The Cockatrice was said to have been hatched from a cockerel's egg incubated by a serpent or toad. It could either kill (through poison) or petrify its victims by its glare, touch (peck), or breath.
In any event, I think the common consensus is that the Cockatrice is half rooster, half serpent, and for gaming purposes retains a separate identity from the Basilisk.
One of the things that is difficult about the Cockatrice for scale comparisons, is how to interpret how big the thing is. In the Monster Manual, it is just listed as small. I have found other sources claiming Cockatrice are 3' high. Various Medieval illustrations indicate people envisioned Cockatrice as being fairly large. I'll stick with this interpretation, but obviously it can be whatever you want.
Two larger miniatures are the Citadel Cockatrice (C29 Large Monsters), and the Grenadier Cockatrice (Monster Manuscript Vol.II 1502, MM13). The Citadel miniature is a beautiful sculpt, though the wings were awful. I just wish that it was about half the size that it actually is.
Next are three smaller miniatures that look closer in size to how Cockatrice are depicted in medieval manuscripts. The first one is from Grim Reaper Casting (Nasteez 1105) now produced by Perth Pewter (N105). The second is from Reaper (Dark Heaven Legends 02631), and the final one is from Ral Partha (All Things Dark and Dangerous 02-962).