Why did it take mathematicians so long to discover non-Euclidean geometry?

Euclid's first two postulates arguably also fail on the sphere, even if we allow that great circles are lines.

Euclid's first postulate essentially says that there is a line between any two points, and one could argue that a unique line is meant. This is false on the sphere where antipodal points are connected by many lines.

Euclid's second postulate essentially says that a line segment can be extended indefinitely, which could be taken to mean that space must "go on forever", which the surface of the sphere does not (without repeating itself).

Furthermore, the identification of great circles with lines is itself problematic since it assumes a non-trivial definition of a straightness other than that of Euclid. Euclid's definition that "a straight line is a line which lies evenly with the points on itself" is hardly sufficient to single out great circles, and even Archimedes's definition "that among lines which have the same limits, the straight line is the smallest" is insufficient by itself since great circle arcs greater than half the circumference are not the shortest distance between its endpoints.

In a sense, Euclid himself realized this. He set the 5th postulate apart from the other four, was not completely satisfied with it, and invoked it only after his first 28 propositions. It was debated in his time about whether the fifth postulate was necessary. In and after his time the fifth postulate was not considered as intuitive or as central as the other four postulates.

In spherical geometry, a line is not a line as the ancients understood it, but a great circle. Ok, we say in hindsight, but a line is an undefined term, and great circles satisfy all the axioms that lines should. But this sort of ontological issue would have been extremely confusing before we had the right language to think about math in.