This page of the guide to Final Fantasy 7 Remake has a walkthrough for the Chocobo Search side mission available in Chapter 14 - In Search of Hope.
Madame M. will assign you with this task. The Woman will tell you about the thugs near Aerith's House. Gothere, threaten your opponents, and Tonberry will come at you. This opponent is unique. You have to watch out for him, but if you understand how this opponent works he won't cause you much trouble.
The biggest threat are his knife attacks. He can kill your character with a single blow. Another one of his moves is block. If he stuns you, he will slowly approach you to execute you. If you're already familiar with enemy attacks, consider what you can do. First of all, you have to keep a good distance from your opponent and always attack him from behind. Avoid all his attacks and don't let him stop.
If you fill the Limit Break use it right away. Don't use the remaining skills. They can be used against you.
Once the opponent is defeated, you complete the mission.