I can't help with the rhyme, but I'll look in the Last Stronghold when I get home to see if it's there.

For the reason behind the "Dark" haired man/woman to do the first footing, we have to go back around a thousand years. The Celts who lived in the Northern Scottish region was subject to predation by the Norse Vikings. According to legend, most of those people were fair-haired,or red-haired, whereas the Celts were dark haired.

So... if you were after good luck, the best would be if the first and all visitors were dark haired.