Without Surf: Go west of Lilycove to Route 121, and a L26-28 Wingull can be found in the grass with a 9% Spawn rate.
With Surf: Surfing within Lilycove itself yields a L10-30 Wingull with a 35% spawn rate, and L25-30 Pelipper with a 5% Spawn rate (which are technically 'the nearest Pokemon that can Fly' if your starting point is Lilycove).
Alternatively, in the Safari Zone, if you don’t want Wingull/Pelipper:
- L25 Doduo or L25 Natu (which requires 1 level up to evolve into Xatu, which can learn Fly) can be found in the first Safari Zone area, each with a 10% spawn rate.
- L27-29 Doduo can be found in the 3rd Safari area with a 15% spawn rate.
- L27-29 Dodrio can be found in the 3rd Safari area with a 5% spawn rate.
- L27-29 Natu can be found in the 4th Safari area with a 15% spawn rate (requires 1 level to evolve and learn Fly).
- L29-31 Xatu can be found in the 4th Safari area with a 5% spawn rate.
- L35 Hoothoot can be found in the 5th and 6th Safari areas with a 5% spawn rate.
Personal recommendation:
If you just want a Fly HM slave: go with a Wingull.
If you’re after something with a bit more grunt: Doduo/Dodrio is fast + packs a punch, and is probably better than the other options as you already have 4 special attacking Pokémon on the team (well, 2 mixed in Blazekin/Marshstomp and 2 Special in Grovyle/Kirlia). Plus Dodrio wrecks Ghosts, though in Emerald, 2 of 5 of Phoebe’s Pokémon carry coverage moves against birds, so it pays to be careful (1 Banette has T-Bolt and reasonable Special Attack, 1 Dusclops has Rock Slide and reasonable Physical Attack).
If you end up going with Doduo: I would recommend withholding its evolution (ie mash B on evolution screen) until level 37, so that it can learn Drill Peck earlier (instead of waiting until level 47 as Dodrio).
