My first shiny was a Zubat in FR but I was rushing through Mt. Moon and accidently ran from it.
My next was a Rattata also in FR but it was on Route 1 and I had no pokeballs.
My first shiny that I caught was a Bellsprout in HG on the route east of Mahagony. The story is this-
I was going through the route and I just wanted to check the grass pokemon for fun when this came out.