"What I want to know is (and have yet to find a satisfying answer to): How did alphabets get to have difinitive 'Alphabetic orders' long before literacy (much less dictionaries) became common?"
Probably from people like us, lovers of the language(s) playing about.
As an example of an early alphebetisation, we can go back to the Old Testament, Book of Psalms.
Psalm 119 is an acrostic (in the original Hebrew), being 176 verses in 22 blocks of 8.
The first block all start with the Hebrew letter Aleph, vv 9-16 with Beth, 17-24 Gimel, et seq to the last 8 verses starting with Tav.
Each verse also includes a reference to the word of God, or his laws/precepts. (with one exception which I leave to the reader to find!)

Of course, someone may be able to find an earlier example!