It depends on the play through. Whilst I've only once had a Fighting-type move (and Pokémon, a Machop) available, that was actually the easiest one as my entire team had randomly turned out to be female, removing the Attract issue. Other times yeah, it was tough to face a Pokémon that strong - especially as I tend to delay evolution in order to enjoy my Pokémon in their cute forms for longer (especially in Johto, knowing I'll have a whole other region to explore once they're fully evolved).
Yeah, Bugsy's Scyther is tough in the remakes. That STAB U-turn is by far the most powerful attack you face in the early phase of the game, and that Technician-boosted Quick Attack means even picking Cyndaquil isn't a guarantee for success (unlike Sinnoh, where Monferno sweeps Gyms 1 and 2, as well as obliterating Maylene's Lucario with Mach Punch). I don't help myself as I have an aversion to picking Pokémon that weren't introduced in the region I'm playing (although I made an exemption recently for Machamp and Gengar given I never had trading available on GBA). A previous team of Chikorita (possibly evolved to Bayleef), Slowpoke, and Togepi really struggled. Although in my most recent one I think Togepi OHKO'd Scyther with some Metronome madness!