I got passed the part where the guys are shocked that he showed himself, I have no idea what to do next. If it helps, I also got to the part where Cheren gives my surf and tells me to explore, and I did. But what now? When and where can I catch him?
While heading towards Lacunosa Town (yes that's your next stop) you will find yourself traversing through Route 13. As you're heading towards Lacunosa/Giant Chasm you should see it right in front of you. All you have to do is walk up and press A to start the battle.
Here's a picture for more precise location:
Hope I helped!