I would need to know more information about your file -- more than is appropriate for a question on a site like this perhaps -- to speak with any confidence about your admissions chances. But here are some broad strokes:
Applying to a top tier school isn't any harder or any different than applying anywhere else. It just involves some more mouse clicks and paying some application fees. If your local academic advisors think you have any chance at getting into a top place, why not apply? In general you should apply to 5-10 places and include "several tiers". If the top places show no interest, there's no harm done. They're not going to give you any negative feedback.
At my University, I earned a transfer scholarship as well as a scholarship from the DoD, in exchange for going to the DoD lab in the summer for research in constructing algorithms.
That sounds very impressive...for some graduate program. A top program centered in pure mathematics may not give you that many points for working at the DoD or constructing algorithms. But other departments would.
I have 2 REUs in discrete structures, one with applications in physics from a top 20 school. The dean of admissions there told me when I went there over the summer that I was the only CC student there in the history of the school's REU program. He said my statement of interest was well written.
I am puzzled that the dean of admissions was involved in an REU. In my experience these are sponsored by the NSF and all the admissions work is done by the faculty PI and/or her hand-picked co-PIs / assistants. Was this in a math department?
I will graduate 3 semesters from now due to taking interdisciplinary coursework. I have finished most of my math requirements, including netting A's in linear algebra, the real analysis sequence, and a graduate discrete course. My GPA is ~ 3.85 as of now (slightly higher).
FYI, except for the graduate discrete course -- what topics did you cover there? -- this is all coursework that candidates admitted to top math PhD programs have done in the first year or two of their undergraduate career, or in some cases in high school. (I for instance did my PhD in a top three math department. I took linear algebra in high school. In my freshman year I took a real analysis sequence which included metric spaces, Lebesgue integration, some Fourier analysis and calculus on manifolds. I was admitted in 1998...before there were treasure troves of mathematics available on the internet. Nowadays a small but non-negligible percentage of people arrive at university knowing most of what I did when I graduated.)
This is not meant to discourage you, but only to tell you that you have just begun to take the appropriate coursework. You should load up in the coming semesters to have a reasonable shot.
Does my CC past and my remedial courses poison my application?
While it would be hard to argue against a strong pedigree, the answer to this is a clear no. Even the brightest admits to a PhD program still have much to learn...as in long years ahead of them. Most admissions faculty are interested in your trajectory as well as your position. From that perspective, if you are doing rather well now then the knowledge that you came from very humble beginnings makes your trajectory look better. Nobody cares about what you did in high school because you need to have moved far beyond it anyway. Graduate admissions packages almost never include information about SAT scores, so even if the admissions personnel saw them they would almost certainly ignore them. They can do that because they will have your GRE scores to look at.
To be honest, I suspect that perhaps you do not know what it takes to get into a "top tier math department". Maybe some faculty around you do; if so, they can be a great help to you. It is not even clear to me that you really want to pursue a PhD program in mathematics: maybe also CS or engineering / applied sciences? That's worth serious consideration. Anyway, even a third tier PhD program is a serious place and could launch you into a promising academic career. You should apply relatively widely, get into the best program that admitted you and is a good fit for your interests, and take it from there.