I'm convinced that the best way to teach stats is to start people with data and graphing. The formal mathematics of statistics is certainly a fascinating discipline (my grandfather was a professor of statistics) but for the rest of us, the formulas are a work-around to the problem of dealing directly with the data and doing repetitive calculations by hand.
The formulas and proofs are certainly valuable, but could come later. And the graphs remain useful (at least for a hack like me) for confirming our understanding of the formulas.
Also, data and graphing would be a way to ease students into programming.