You'll need to leave Mauville City going east onto Route 118, then be able to Surf over to the other side of the route. So the soonest you can do this is after you get Surf from Wally after you beat the Petalburg Gym.
At that point you'll go back to Mauville and can exit towards Route 118. Surf to the other side and speak to the fisherman NPC and he'll give you the Good Rod for free. This is the same for both Omega Ruby and Alpha Sapphire.
(Source: Guide Strats)