One thing that I'm quite happy with in my physics education is that the faculty went to quite some effort to make sure that the math and physics tracked each other so that you would see the theory and practice twice and intertwined.
One thing that was missing (as other's have mentioned) was numerical methods and programming techniques, which I think could also be covered in a parallel track.
You can introduce Lagrangian and Hamiltonian mechanics very early on if you're okay with hand-waving over some of the analytical details and presenting it mostly as a problem solving tool. E.g. David Morin's Introduction to Classical Mechanics does a great job with minimal formal prerequisites (freshman calculus is adequate for the majority of the book) though its exercises and problems, which are the book's highlight, will be too challenging for most freshmen.
I think a low-brow problem solving centric approach is ideal as an introduction to Lagrangian mechanics in particular (not so much Hamiltonian mechanics) since the advantages are so stark and obvious compared to the Newtonian formalism. You don't have to worry about how velocities and forces transform to write down the equations of motion. You just write down the Lagrangian and take derivatives. That's something every student will immediately appreciate.
We might have a good approach to classical physics - though I wouldn't bet on that, may be we really should teach classical mechanics closer to SICM, by Sussman, approach. But quantum physics leaves doubts even with undergraduates majoring in physics.