I put together a list of potentials. Horsea, Aron, Cacnea, Feebas, Spheal, Shinx, Budew, Combee, Blitzle, Cottonee, Tynamo, Skrelp, Clauncher, and Bergmite.
Obviously any that are already in the game would need replacements.
Shinx I suggested 'cause I figured it's pretty popular but also frustrating to get.
Budew I particularly like as a candidate seeing as Roserade is a very popular pokemon, Budew is already implemented in the early game and isn't out of place there, the existing Budew could be replaced with Pansage which would allow all three of those monkeys to be obtainable pre-first gym, and you get to charge people money for Budew.
Combee would need to be taken out of the headbutt-able trees otherwise there's no point to the event, but it would draw more attention to an underrated early game pokemon.
Blitzle is a particularly strong contender in my mind.
Bergmite could be a bit overpowered. Well, not Bergmite, but Avalugg. Still, there is a shortage of ice types in the early game.