These are (apparently) the areas in Galbadia where you can run into them:

  • Shenand Hills
  • Winhill Bluffs
  • Humphrey Archipelago
  • Lallapalooza Canyon
  • Monterosa Plateau

Not sure how many of them you can get to that early but hopefully it will help. Also from personal experience I think you can fight them on the grass in the dusky part of Galbadia near Deling City.