I appreciate the appeal of your question. I was a philosopher before I began seriously studying mathematical physics, and even though I had already considered the basic questions, I found myself struck anew by the regularity with which nature has been found to conform to the most abstract imaginative leaps of rare minds.
Nevertheless I believe that the question is more to be dissolved than solved. It is akin to the question of how language can "latch onto reality" (the answer to which lies in understanding our own behavior).
Some of the questions you ask (e.g. "why should the universe be comprehensible at all?") may be illuminated by evolutionary considerations. An amoeba responding to being poked is already "comprehending" (a tiny piece of) the world in a sense, and higher animals display a finely-tuned set of useful, reality-conforming behaviors requiring discrimination and goal-pursuit. Their mental constructs "conform to reality" because (and to the extent that) they worked in the past (and others didn't). (And of course we know that past results are no guarantee…)
At the same time, it helps to be aware that we have no idea what it would mean for the universe NOT to be AT ALL comprehensible. We can contrast understanding here with ignorance there, or complete understanding with partial understanding; but we have no concept of a world without any understanding at all. So this is why I say that your question is at bottom a pseudo-question (which may nevertheless be very educational and fruitful along the way to being dissolved).
I don't think your 4 positions are exhaustive. I'd say you're missing a position of Realism, which says that mathematical structures inhere in nature, without requiring any "independent realm" to give them "reality". It is nature that gives them reality. For we cannot conceive of a nature without mathematical structure--without unity and multiplicity, spatial orientations, boundaries, sets…
And by the way I'd like to add this open-ended list of mathematical categories to your account of the natural genesis of mathematics out of counting. Not just counting, but geometrical intuition and discrimination of natural sets seem to me to be equally grounded in an evolutionary account.
You say that a theistic picture is tidier than the others, but are afraid of embracing religious baggage. I do think that a Spinozan patheism is a viable solution, as long as you realize that it is really nothing more than a counterweight to the kind of materialism that denies any structure or intelligibility to the world independently of humans. To call the world "divine" in this sense is just to acknowledge that before intelligent beings, the world already had intelligible structure, and contained the potentiality for the causal generation of intelligence.