That said, I might push back on the idea that CG problems don't have this kind of regularity. They give the example of a point being either on a line determined by two other points, or to one or the other side of it. They say that you need to know this information exactly, which is combinatorial.
It's not so clear to me that you really do need to know this information. For this example, you could represent the line as a zero level set, and then the query above is answered by the sign of the value of the zero level set function evaluated at this point. There is some latent numerical error here, but this problem is well-conditioned in the sense you mention above.
I think it would be interesting to see whether it's possible to build a library of CG routines based on a "fuzzier" level set conception of things.