This proposition has been concluded without the use of the parallel postulate, because the first time Euclid invokes the parallel postulate is in I.27. Thus, it should apply to all geometries satisfying the other axioms, namely elliptical geometry.
How is not a very large triangle in elliptical geometry not a counterexample to I.16? Take a triangle that nearly stretches over a hemisphere and the interior angles will each be nearly 180 degrees, leaving exterior angles nearly 0. Clearly, 0 is not bigger than 180.
Thanks for reading!