How old could population I stars theoretically be? What's the earliest they could have formed?
Since Pop III stars are the oldest stars, then they could have theoretically began to form in the Cosmic Dark Age (CDA), see section 5, since the oldest galaxy we've observed so far (in infrared) is about half way through the CDA (~$480$ million years). As the article states,
Stars and galaxies are formed when dense regions of gas form due to the action of gravity, and this takes a long time within a near-uniform density of gas and on the scale required, so it is estimated that stars did not exist for perhaps hundreds of millions of years after recombination.
So not only must the temperature of the universe be sufficiently cool, gravity must have acted for a long enough amount of time for baryonic structure to begin to form.