once you meet the three legendary dogs, there all in a random location all over johto, luck is the game for them when you see them i reccomend using quick balls or a masterball if you so please, for the legendary birds, since you have gold, i say the radio man gave you a rainbow wing, go to thw tim tower, which is located in the same city as theburned tower where you first saw the dogs... to catch lugia, you need to beat the pokemon league first, then when you can to go the kanto region, go to pewter city, there should be a old man near the market, talk to him and you shall recieve the silver wing, then go back to johto, on the whirpool islands, make your way through and lugia should be there