To confirm again: Yes, Lugia's shininess is determined as soon as you encounter it. I know this for a fact after having encountered one in Crystal. (Yes, yes, I know it's "pics or it didn't happen" for things like this, but trust me. Lugia and Ho-oh are not among those Pokemon whose shininess are determined at the start of a new game.) If you'd like concrete proof of this, try doing a search for Lugia and shiny ratios on Google. *shrug* Or I could do it for you. Either way.
In any case, the problem is that shinies are incredibly rare in the GSC era (even moreso than they are nowadays, if I recall correctly), so you'll be soft resetting for awhile.