I wonder if the Minoans on Crete predate the Phoenicians in Lebanon.
Good question. They did. Minoans seem to have been all over the western Med first as well.
According to R. W. Hutchinson, Prehistoric Crete (1962), there is no definite evidence for people in Crete in the Paleolithic period but acknowledges that the average archaeologist working in Crete might not recognize a Paleolithic artefact. I don't know if the picture has changed since 1962. Sir Arthur Evans found evidence of Neolithic habitation at Knossos. The Neolithic seems to go to about 3000 B.C. when the Early Minoan period starts. When the Neolithic era on Crete began is unclear. J.D.S. Pendlebury (a noted British archaeologist who was killed in the German invasion of Crete in 1941) says that Evans suggested that the Neolithic may go back as early as 8000 B.C. but Pendlebury thinks the earliest Neolithic settlers arrived at most a few centuries before 4000 B.C.
It may be that recent studies of the spread of farming from the Near East to Greece and Crete may give a clearer idea of when there were Neolithic inhabitants on Crete. They seem to be ancestral to the later Minoan population (but immigrants from Asia Minor could have entered Crete later as well).
The heyday of Minoan civilization is after 2000 B.C.