Rust monsters first appeared in Supplement I: Greyhawk. Their essence remains unchanged, but a lot of detail has been added. They are now said to dwell only in subterranean places, and have an acute sense of smell when it comes to ferrous metals. They have also been nerfed a little bit: magical weapons now get a saving throw to avoid the rust effect. The rust monster is also significantly faster than it used to be, making it even less likely that an armoured fighter can outrun it, but some guidelines have been added for dropping metallic items to distract them.
Also, both mithral and adamantite are said to be steel alloys. This takes a little of their mystique away, to my mind, but there it is in the book. I just report it as I see it.
Movement: Old - 12"; New - 18"
Sahuagin first appeared in a mammoth entry in Supplement II: Blackmoor, and much to my chagrin the Monster Manual is equally wordy on the subject. They remain the same sadistic, predatory fish-men of the sea, but Gary has availed himself of the chance to change a lot of things about them.
Though we already knew they lived in the sea, it is revealed here that they prefer warmer waters, and that they generally stick between 100' and 1500' sea depth. That they hate ixitchachitl (the rad manta ray vampire philosophers) is also new. The social structure of the sahuagin is retained, with nine princes all ruled over by a king, but here we discover that this is supposed to mirror the planes of Hell, as sahuagin are devil-worshippers.
The organisation of sahuagin lairs has also been re-jigged, but the general make-up is the same. The more sahuagin there are, the more tough fighters and clerics they have. The only real difference is that there are no longer any sahuagin magic-users. The clerics are all female (shades of the drow, though sahuagin predate them). We also learn that sahuagin villages are domed, but that's par for the course for underwater villages. Their numbers have also dropped quite a bit. Their capital now has 5,000 residents, instead of nearly 100,000.
Previously sahuagin were mostly armed with tridents and barbed nets. They now add spears, javelins, daggers and special underwater crossbows to their arsenal.
Their physical appearance has changed quite a bit. A lot less detail is given in the Monster Manual than we got previously, but the main thing to note is that they no longer have tails, and they have clawed hands instead of pincers. I can see why Gary got rid of the tail, given that it inflicted 2d6 damage (a pretty hefty amount for that stage of OD&D). And it's probably hard to wield nets and tridents with pincer hands.
In Supplement II, sahuagin were said to have been created by evil gods when the world was flooded. Gary has retained that idea as a possibility, adding that the gods made them out of a nation of evil humans. It's also said that the tritons believe sahuagin are related to sea elves, and claim that the drow spawned them. (It's another early drow sighting, before they have officially appeared anywhere).
No. Appearing: Old - 10-60; New - 20-80
Armor Class: Old - 4; New - 5
Movement: Old - 18"/30"; New - 12"/24"
Hit Dice: Old - 2; New - 2+2
So the situation we have is that sahuagin have become less numerous, slightly slower, slightly tougher, and have lost their tails and pincer-hands. The loss of the tail helps explain the lower speed, but opens a more difficult problem, as the physical changes require a greater explanation. I keep coming back to the idea that they were created by evil gods; after all, if that's the case there's no reason they can't be recreated. I can even tie it into the lower population levels: after a series of disastrous wars against tritons and ixitxachitl, the sahuagin turned to their devil masters and were changed into stronger forms. Their magic-users were offered as sacrifice, and that explains why they're all gone as well. Voila, problems solved!