Legendaries were very hard to catch, especially after Gen II. Sometimes, however, we got lucky and caught them in the first few balls.
What would be your easiest (shortest amount of time) capture of a Legendary Pokémon?
One I could mention is the capture of Ho-oh in HeartGold after 5 Dusk Balls. And Reshiram and Zekrom.
EDIT: So many things about Reshiram and Zekrom. If you do a little research about them (and Dialga and Palkia), you know that their catch rate is 45, I believe, not 3. Dialga and Palkia's is the same as Chatot.
If you want more information about catch rates, go here. Anything that has a catch rate of 3 (excluding Beldum, Metang, and Metagross) you can choose from. Remember, no Dialga, Palkia, Reshiram, Zekrom, Mew, Celebi, Jirachi, Shaymin, and Victini.