The first main-series game to have a different piece of music when battling legendary Pokemon was Crystal. However, I'm pretty sure that the only time that this music was played was when battling Suicune.
Sources: The track listing comment this YouTube video, as well as the track listing comment on this YouTube video.