Well, there’s actually all kinds of ways to break Euclid’s axioms. Curvature is just the least exotic. Ultrametric spaces, to give just one example.

The cubes look a little funny, I guess.

I believe the horror of those structures in the story arose from the fact that it looked euclidean, but didn’t feel euclidean, like there was some weird curving going on that the human perception isn’t equipped to grasp.