I'll definitely go with clarity as the overriding criterion. In the case of the third floor gallery I would say that if the gallery in question were a floor gallery and there were at least two others then there could be some confusion as to what third floor gallery meant. Since this is unlikely to be the case I say don't bother putting a hyphen in there.

Regarding the easily remembered rules, easily is an adverb (the -ly rule is an oversimplification; there are adverbs that don't end in -ly, e.g., well and words that end in -ly that aren't adverbs) and adverbs modify verbs, adjectives and other adverbs. Thus in the easily remembered rules, easily cannot modify rules; no ambiguity, no hyphen.

The hyphen has also been used to link separate words that form a single concept in a transitional form between the concept as a two word phrase and as a single word. Baseball used to be written Base Ball, two words, no hyphen. It is presently universally written as one word (by such people with enough good taste in sports to write the word at all). There was a fairly long period from the late nineteenth century to the early middle twentieth when both forms were in use and it was also written base-ball.