You could try a problem-based approach. Just in case you don't read the rest of this answer, let me offer a couple of links:
Phillips Exeter's math curriculum is entirely problem-based, up through multivariable calculus. Exeter offers their curriculum to the public for free, just click on "Teaching Resources" and download the problem sets. For a first-year calculus course, I recommend the Math 4 problem set. Yes, this course is aimed at high school seniors, but they're Exeter seniors---they're basically college freshmen.
If that's not rigorous enough, try the University of Chicago's Honors Calculus sequence (the link takes you to one of the instructors' course site). Read the syllabus first, then download the sheets.
In problem-based (or "inquiry-based") learning, rather than saying "And now, our next theorem is Basson's Irrelevance Theorem; here's its statement and here's its proof," you instead pose a series of problems that the students must work on and prepare before class. Perhaps the problems are similar to the ones that Basson was trying to solve when he developed his famous Irrelevance Theorem; perhaps they are special cases of the Irrelevance Theorem, leading up to a general case; perhaps they simply guide the students towards some concept.
In any case, in the next class, students are asked to share their solutions with the group. They may not have a complete solution, and this is ok. They may have only part of a solution, in which case they should say "I got this far, now what?" This motivates a discussion of the merits of the various approaches, guided by the instructor ("Thank you for proposing that approach, but have you considered this wrinkle? How does that affect your solution? Is there an alternative approach that takes this into account?"). By the end of the discussion, the group has arrived at a solution and can move on to the next problem.
A problem-based approach has several advantages:
- It comes with relevance built-in. You develop theory as it's needed to solve problems, not the other way around. This is, of course, how real mathematics is done.
- Related to the last point, it gets the students actively involved in doing mathematics, rather than seeing it done.
- It reveals the truth about math research: it's messy, you rarely figure out the right approach the first time, and proofs don't just come pre-fabricated in their most elegant forms.
- Sure, it's messy, but it's also so effective. After all, it's by going through the struggle that you really learn math. The students come away with a much more complete understanding of the material, an appreciation for why theorems are stated the way they are, for how everything fits together. They develop a sense of ownership over the material that can only come when they've actually developed it themselves---in collaboration with others, sure, but in contrast to having someone simply give them the results.
The theme here is that students learn math by doing math. The class time is mostly discussion-based, and the students are the most active participants in the discussion. The instructor is a guide or facilitator, to help students see flaws in their reasoning, to bring up potential issues or edge cases that might not occur to them, etc. On a really excellent day, the instructor practically doesn't even have to be there.
- It's a seriously creative challenge to put together such a curriculum. You have to pick good problems, ones that challenge the students without overwhelming them, that lead them through the content you want them to learn, and that motivate their interest. Not every problem will do all three of these things, but that's what you should strive for. Use the links above for inspiration.
- It requires small classes, which means it requires a lot of instructors (hello, graduate students!). You simply can't pull off a discussion with 500 people in a room. You need to aim for more like between 10 and 20 students in a room.
- Students struggle at first to get used to the classroom dynamic. They're so used to passively absorbing the instructor's lecture, and they are initially uncomfortable sharing math in public, being wrong in public, not knowing if they have the "right answer", etc. With the right classroom management on the part of the instructor, the students get over this struggle, and the rest of the year is amazing.
- It can be a tough sell to instructors, who are used to a certain way of teaching. It places the emphasis on the students rather than the instructor, and this spooks some people who are used to having (and in some cases, enjoy having) control over the class. If the students are struggling with a problem, it takes a lot of self-discipline not to simply present the solution to the class. In short, it's a completely different approach to teaching, and this is hard for some people to learn how to do.
I'll end this by saying that in my opinion, the pros far outweigh the cons. As far as the last con goes, if you're considering a radical revamping of your curriculum anyway, you can probably get the requisite buy-in from your instructors. Best of luck!