The other two puzzles are accessible only by going through Union Cave, and you need Strength for at least one I think. When you get near to the southern exit, go to the bottom-left hand corner of the cave. You should find a ladder going down. Go down it, and there's a patch of water. Surf across and up and you'll end up on land. There are two Hikers here and a Cooltrainer (I think) near the initial ladder. Go through the path and either go to the top or the bottom exit. The top exit leads to the patch of grass where you can catch Smeargle and Natu, the bottom leads to the door you saw at the top of the ledges.
It's a bit hard to explain, but if you look you'll probably find the place I'm talking about.
