I think we make this harder than it has to be, by not doing proof-based math earlier.
Real analysis is often the first class in a math bachelor's program where things really get far from intuition and much harder to wrap your head around than the material from earlier classes.
Making that the first proof-based class is just piling one hard thing on top of another.
I think we'd be better off if we made basic calculus proof-based, at least for people such as math majors who are going to need to learn to follow and do proof-based math at some point. For those going into fields where they will not need to read and do proves, have a separate "practical calculus" track.
You can start out with more informal proofs at the start of basic calculus, and slowly step up the level of rigor throughout the year.
I did quite like Bartle's "Introduction to Real Analysis" and "Elements of Real Analysis" books, kind of surprised that nobody else has brought them up. I think they strike an excellent balance between rigor and actually being comprehensible and approachable to people that aren't already familiar with proofs.