Ok, I'm replaying the game (a good thing in itself, because FFVII is awesome), and so far I've chronologized the list up to Rocket Town.
You can't get any until after you leave Midgar.
Matra Magic: From Custom Sweepers in the dark wasteland area outside Midgar.
Lv4 Suicide: From Mu's in the grassy areas between Kalm and the Chocobo Farm.
Chocobuckle: From level 16 Chocobos around the Chocobo farm, after giving them a Mimmet Green and using Lv4 Suicide on them.
Beta: From the Midgar Zolom when he's at low health. Does a ton of damage, so bring Elemental-Fire/Ifrit in your armor or a Fire Ring.
Flamethrower: From the Arc Dragons in the Mythril Mines.
Acquire second Enemy Skill Materia in Junon.
Laser: From the Death Claws in the Corel Prison. (Bullmotors in this same area also use Matra Magic, which you can get here for your second ES Materia)
Aqualung: From the (Damn, forgot the name) in the desert around the Golden Saucer (you can actually get this one before acquiring the buggy if you leave Corel and head to just the right point on the desert's perimeter). Another heavy damage one, but nowhere near as deadly as Beta. Still, you don't have a water elemental materia to put in armor yet, so it will do a fair amount of damage.
White Wind: Bactrack to the area around Junon and Manipulate a Zemzellet.
Frog Song: From Touch Me's and Toxic Frogs in the jungle around Gongaga.
Death Sentence: From the GI Specters and Sneaky Steps in the Cave of the GI.
Trine: From the Materia Keeper in the Nibelheim mountains (limited acquisition ability!).
I will add more as I progress if people are still interested.