If Stone Edge existed in RBY I doubt anything other than Rhydon/Golem/Onix would get it unless it was a TM. For the sake of making this discussion relevant though, I will assume the new gen compatibility applies.
I don't think Aero would be broken enough to be banned (we're also more ban happy now that we were back then). It has strong checks on Rhydon and Golem and you won't want to give them many openings. Other than that, it's a frailer but even more scary version of Tauros so I'd say it would become nearly a staple, although not quite on the level of Tauros (who is still a good matchup vs Golem/Rhydon/Aero). It should be noted that Rhydon will only crit with SE around 60% of the times and Golem around 70% of the times (less factoring in accuracy).
Tauros would just drop EQ for SE.
I definitely would see Alakazam, Zapdos and Jolteon droping in usage. Snorlax would go down a bit and would start using Blizzard or Surf over Earthquake or Hyperbeam. Exeggutor would become even more of a staple than it currently is, Golem/Rhydon would be seen more often than not, and Slowbro would go up as well. Starmie maybe too.
Sandslash becomes interesting as a decent check to the three rocks in one, but not more than that since it still has trouble with its usual checks. You could make a case for Machamp and Hitmonlee, who may go up to the level of Kingler-esque gimmicky stuff. I see Gyarados becoming a bit more threatening and Dragonite has an alternative to the wrap set. Speaking of wrap, its usage would probably drop a bit. Kabutops also becomes interesting with a non-SD set. A few random UU mons might become a bit more usable following the sped up of the metagame and the likely tendency of dropping a recover user or Snorlax for a rock type. Apart from the ones already mentioned Nidoking comes to mind due to being able to use Stone Edge but you could also make a case for bulky stuff like Clefable or Poliwrath.
Reflect Chansey and tanklax would probably become extint and Nails would be in absolute ruins.
I don't think Aero would be broken enough to be banned (we're also more ban happy now that we were back then). It has strong checks on Rhydon and Golem and you won't want to give them many openings. Other than that, it's a frailer but even more scary version of Tauros so I'd say it would become nearly a staple, although not quite on the level of Tauros (who is still a good matchup vs Golem/Rhydon/Aero). It should be noted that Rhydon will only crit with SE around 60% of the times and Golem around 70% of the times (less factoring in accuracy).
Tauros would just drop EQ for SE.
I definitely would see Alakazam, Zapdos and Jolteon droping in usage. Snorlax would go down a bit and would start using Blizzard or Surf over Earthquake or Hyperbeam. Exeggutor would become even more of a staple than it currently is, Golem/Rhydon would be seen more often than not, and Slowbro would go up as well. Starmie maybe too.
Sandslash becomes interesting as a decent check to the three rocks in one, but not more than that since it still has trouble with its usual checks. You could make a case for Machamp and Hitmonlee, who may go up to the level of Kingler-esque gimmicky stuff. I see Gyarados becoming a bit more threatening and Dragonite has an alternative to the wrap set. Speaking of wrap, its usage would probably drop a bit. Kabutops also becomes interesting with a non-SD set. A few random UU mons might become a bit more usable following the sped up of the metagame and the likely tendency of dropping a recover user or Snorlax for a rock type. Apart from the ones already mentioned Nidoking comes to mind due to being able to use Stone Edge but you could also make a case for bulky stuff like Clefable or Poliwrath.
Reflect Chansey and tanklax would probably become extint and Nails would be in absolute ruins.