In the 5th gym city, near the gym, you can surf to a small island with a lighthouse. The item on said lighthouse is in fact a Water Stone.
Once you leave Sky Arrow Bridge and enter Hiun City, visit Pier 1 (left-most) and talk to the scientist. Choose the first option for a Leaf Stone, second for a Fire Stone or a third for a Water Stone. This will work only once (you can't take all three items)