Rigorous proofs can be introduced in many courses. Personally, my first course making a large emphasis of proof was real and complex analysis (which was the calculus course), then linear algebra. I also took “discrete mathematics for computation”, a course specifically aimed towards computer science students, but that course was so chock-a-block full of content that there was no time for proofs.

I find discrete mathematics proofs very doable and useful, but pretty boring compared to analysis and algebra, and I very much enjoyed practicing mathematics skills in the latter rather than the former. (This is coming from someone who has published papers in combinatorics).