I was a bit like that in my first three years if study, then I read the first volume of Schwartz' Analysis, where he introduces the ZFC axioms. This is the point when I understood that one simply cannot make sense out of set theoretical axioms before having manipulated higher-level mathematics (here "higher-level" is to be understood in the sense of higher-level programming). The analogy with programming is quite good I think: who would first learn machine language, before learning higher-level languages?
Advanced mathematics consist in both building more complicated structure, and digging the foundations of what has already been built. Students in mathematics should realize that what they feel is well founded in their background knowledge in fact rests on a lot of maths they did not yet learned. Even the construction of the natural numbers is not as trivial as they might think, and in fact they have been used to reason from (high-level) axioms they have accepted. Accepting a Theorem because in some given course its proof is not central as its usage is not that different.
Also, the way one founds mathematics is not that important to higher-level maths. When we do mathematics, we all think in a strongly typed way while set theory is almost not typed at all (with the exception of classes vs sets). As a side note, I am very intrigued by the homotopy type theory as a strongly typed mathematical foundation, but have not have had enough time to dive in it.
As another side note, in the old debate as to which integration theory use in the first undergraduate years, my favorite answer is none at all: state the axioms of an integration theory we need for the course, and wait until Lebesgue integral is introduced. This is a healthy way to remind that we do rely on unproved thing almost all the time; better be warned about it.
At this point, I did not really answered the question. Why not let them read Bourbaki? Either they will end up hating it pretty fast and accept more easily a few result and hand-waving, or they will love it and will learn a lot from it.