My research for my answer to Which alphabet were the original Torah scrolls in? gave me an idea--Since the Early Alphabetic alphabet is also called Sinaitic, and the timing seems about right, maybe the Alphabet was also given at Sinai along with the Tablets and Laws...quite a gift to us and the world! Is there any information in the extant literature on this possibility?
I believe it was used in Egypt, well before the Tablets.
See Shabbos 31a where Hillel the elder implies that the way to read the letters was passed down as an oral tradition. It was always confusing to me how someone can read the first word of the Torah and deny the oral tradition. How did they read the Torah without it?
Also, see Sanhedrin 108 where it is clear that Avraham had the exact text of Parshas Noach (see Yad Rama there where in one opinion he says that they had the entire future text of the Torah Before Sinai!).