Our kids get their math at home; a combination of Singapore math and [Gelfand's algebra][1].
The second ref is the "beuty of math" stuff you refer to; obligatory quote: "Problem 231: Find a recording of Bach's *Well-Tempered Clavier* and enjoy it". Problem level is certainly higher than Kindergarden though. Gelfand wrote some other books aimed at kids, but IMHO the other ones are not that nice. 

  [1]: http://www.amazon.com/Algebra-Israel-M-Gelfand/dp/0817636773