I agree that we should weigh possible foundations against desired results and respect multiple possibilities as you say. However, we need a formalization of this. It might be that 1st order vs 2nd order is not important. I would suggest, however, that the puzzle I presented in the post is important. The proof-theoretic structure of 1st vs 2nd order might not be a big deal. (A learning system which prefers compact first-order theories can learn the desired many-sorted logic.) The structure of reasonable probabilistic beliefs over these two domains, though, is another thing yet! (A learner which prefers compact first-order theories cannot mimic the desired behavior which I described.)

You won't automatically get the desired behavior by constructing some sort of intuitive learner based on informal principles. So, we need to discuss formalism.