As far as a full curriculum goes, I don't believe there is one that does exactly what you want. Books (in the United States, at least) divide into two camps:
"Constructivist" (e.g. Everyday Math, Connected Math)
"Traditional" (e.g. Saxon, Singapore)
Now, any search you make that even has a whiff of these terms will summon up loud and angry missives (try this article from the New York Times for an idea).
Constructivist curriculum is an attempt to catch the "joy of mathematics" approach to learning; for example rather than a worksheet with addition problems there might be a question about all the different possible sets of numbers that add up to 20.
The downside (as pointed out by the article above) is that (especially when taught by teachers who aren't themselves strong in mathematics) it can lead to basic skills being missed.
This is a problem Lockheart's Lament acknowledges. He seems to think students won't miss anything important. This can be true if the person steering the education is a mathematician, but with a non-specialist (i.e. most elementary school educators and homeschoolers) things can go horribly wrong.
Now, it's possible to balance to pull off a fantastic curriculum, but the ones I know about (say, at the Russian School of Mathematics in Boston) are, as self-described by the teachers, not following a curriculum at all. That's great if the teachers are experts, but put homeschoolers in a quandry.
I think the world is still waiting for an inquiry-type elementary curriculum that can be followed by non-experts and doesn't shortchange basic skills. So for now I'd suggest:
a.) Pick a traditional curriculum (Singapore is fine, although do shop around).
b.) Supplement. This very question is filling with lots of suggestions.
First, most mathematicians don't really care whether all sets are "pure" -- i.e., only contain sets as elements -- or not. The theoretical justification for this is that, assuming the Axiom of Choice, every set can be put in bijection with a pure set -- namely a von Neumann ordinal.
I would describe Bourbaki's approach as "structuralist", meaning that all structure is based on sets (I wouldn't take this as a philosophical position; it's the the most familiar and possibly the simplest way to set things up), but it is never fruitful to inquire as to what kind of objects the sets contain. I view this as perhaps the key point of "abstract" mathematics in the sense that the term has been used for past century or so. E.g. an abstract group is a set with a binary relation: part of what "abstract" means is that it won't help you to ask whether the elements of the group are numbers, or sets, or people, or what.
I say this without having ever read Bourbaki's volumes on Set Theory, and I claim that this somehow strengthens my position!
Namely, Bourbaki is relentlessly linear in its exposition, across thousands of pages: if you want to read about the completion of a local ring (in Commutative Algebra), you had better know about Cauchy filters on a uniform space (in General Topology). In places I feel that Bourbaki overemphasizes logical dependencies and therefore makes strange expository choices: e.g. they don't want to talk about metric spaces until they have "rigorously defined" the real numbers, and they don't want to do that until they have the theory of completion of a uniform space. This is unduly fastidious: certainly by 1900 people knew any number of ways to rigorously construct the real numbers that did not require 300 pages of preliminaries.
However, I have never in my reading of Bourbaki (I've flipped through about five of their books) been stymied by a reference back to some previous set-theoretic construction. I also learned only late in the day that the "structures" they speak of actually get a formal definition somewhere in the early volumes: again, I didn't know this because whatever "structure-preserving maps" they were talking about were always clear from the context.
Some have argued that Bourbaki's true inclinations were closer to a proto-categorical take on things. (One must remember that Bourbaki began in the 1930's, before category theory existed, and their treatment of mathematics is consciously "conservative": it's not their intention to introduce you to the latest fads.) In particular, apparently among the many unfinished books of Bourbaki lying on the shelf somewhere in Paris is one on Category Theory, written mostly by Grothendieck. The lack of explicit mention of the simplest categorical concepts is one of the things which makes their work look dated to modern eyes.
Best Answer
Don Zagier has a well-known paper, A one-sentence proof that every prime $p\equiv 1\pmod 4$ is a sum of two squares. An undergraduate mathematics major should be able to verify that this proof is correct. But as you can see elsewhere on MathOverflow, most professional mathematicians are unable to "understand" this proof just by studying it in isolation. By lack of "understanding" is meant, for example, the inability to answer questions such as, "Where did those formulas come from? How did anybody ever come up with this proof in the first place? Is there some general principle on which this proof is based, that is not being presented explicitly in the proof?"