Describing undergraduate applied mathematics and CS as being full of "polished proofs" strikes me as a little surprising: in most American curricula, proofs are soft-pedaled in applied courses as it is something else (the applications?) are viewed as more important. (I am not an applied mathematician. It would be helpful to hear from one.) What you describe sounds more like the educational system in Europe or elsewhere, where at least a veneer or rigor and abstraction seems to be given (for some reason) to students in a variety of applied fields.
As a pure mathematician reading your question, my first thought is to suggest that you go more deeply into the proofs of things and try to learn the hidden motivation. You say "we are not required to understand them deeply", but you are allowed to, right? (I hereby give you permission!)
I know that in some mathematical methods courses for (say) engineering students they just plow through material too quickly for it to really make sense: they may cover in one or two courses what math majors would study over several years: a bit of vector analysis, a bit of Fourier series, a bit of ODEs then PDEs, and so forth. This indeed does not seem to lend itself to understanding. I have often thought that applied mathematicians / engineers / computer scientists must be very bright indeed to get something out of this kind of limited, quick exposure to these rich, subtle topics.
So I would suggest that you slow down and pick at least one topic to pursue in more depth and detail. If you feel like you have a weak background in analysis and algebra, start with one of those. For instance, get a copy of Spivak's Calculus (or, according to your taste, Rudin's Principles of Mathematical Analysis, or Korner's A Companion to Analysis, or....: there are many, many good texts on "elementary, but serious, undergraduate analysis" at this point) and start reading through it and working the problems.
It is also possible that you are not taking the courses that you would most enjoy. Again this depends a lot on your institution and your location: outside of the US, undergraduate programs have lots of required courses and it seems that students are expected to swallow all of them without much choice. At a large university in the US there will often be several different varieties of the same undergraduate course, one of which will be less rushed and superficial than what you describe. As always, contacting a faculty member to make sure that you are fully using the resources of your institution is a good idea.