There's no earliest point in the order of the morning to lay tefillin (as long as it's daylight out) because the time for wearing tefillin is all day.
But, nowadays, the common practice is not to walk around wearing tefillin but just to aim to fulfill the especially-important obligation of having then on during the time of reading the Shma and praying the Amidah (see הלכות תפילין פרק ד הלכה כו).
It is problematic to interrupt Shaharit anytime from Barukh She-Amar onwards (שולחן ערוך אורח חיים נא סעיף ד), so to have tefillin on during Kriat Shma and the Amidah, it seems necessary to lay them prior to beginning Barukh She-Amar (this is just my logical assumption, I don't have a source). Seder Avodat Yisrael places the laying of tefillin right there, immediately before Barukh She-Amar.
In some nusha'ot, communal prayer can start before Barukh She-Amar. For example, to follow the Lurianic custom of reciting Kaddish De-Rabbanan after Korbanot, communal prayer needs to begin with the recitation of Korbanot, or at least some portion of the mishnayot and baraitot in it, to justify recitation of the Kaddish. It then makes sense to lay tefillin before then, so you can continue on without interruption afterwards with Hodu.
I think one very prevalent way of doing things is simply to lay tefillin when you arrive at shul, so that when prayer starts, you're ready to go. But where each shul starts prayer will vary.