They should teach it from the perspective of what problems you are trying to solve, what your options are, and how those options work in practice.
The "in practice" part should be lots of simulations with something like a ChromeBook, so people could really see the ideas working. Create a (simulated) bucket with 70% red balls and 30% blue, then pull samples of various sizes and see how well the sample means match what you already know is the "truth" (70/30). You'll soon have everybody seeing that bigger samples aren't always better, but they tend to be, and they'll see how much better they get as a function of size. Make charts of the improvement. Talk about how good the estimate really NEEDS to be.
Then try some tests where the students DON'T know the "truth" about the population and have to use samples to estimate it. How far off do they think they are. How confident about various intervals, etc.
Then start explaining some of the math that lead to formulas that let you calculate these estimations, sample sizes, confidence intervals, etc.
Have estimation games: you get points for getting an estimate within some delta of the population mean, but you have to pay points to buy your samples. So, how big a sample does your team want to buy?
Then continue with other basic prob/stat ideas such as bayesian cancer tests (does this mean you have cancer or not?) and courtroom dramas (does this mean he's probably guilty or not?), commonly misunderstood situations (ex: Simpson's Paradox), how Gaussian estimators begin to fail when things aren't independent, and all sorts of other introductions to quantitative thinking about real life scenarios.
I was a very math oriented student at a high school with a heavy bias towards liberal arts ... So when it came to picking senior year electives, I was delighted to enroll in AP statistics.
The classes turned out to be tutorials on the built-in TI-83 stats functions, with step-by-step instructions on how to answer the various types of questions we would encounter on the test. I forgot everything and gained virtually no statistical intuition.
Thankfully I had a similar experience to you ("Probability and Statistics for Engineers") with a fantastic professor who researched computer networks. His lectures were sprinkled with tangents tying the current topic back to his own field / research, which to me made the biggest impact. Contextualizing a taught subject markedly improves the course experience.
Fortunately, I had a great professor in Calc III who more than made up for this.
I took a fantastic one-off class as an undergraduate called, IIRC, "Statistics for Physicists". The class taught us Bayes' Law, what tests were, what significance was, and how one might go about deriving and using simple tests. Everyone came out of the class with a very clear understanding of what statistics meant, and no one who took that class would take a statement like "this drug had a significant effect on such-and-such" without an appropriate grain of salt (specifically, how big was the effect). The class didn't include a giant grab-bag of tests.
One of my friends took a regular introductory stats class the following quarter. At one point, he asked me if I could help him do a such-and-such test (Student's t, maybe, but I don't remember which one). I asked him what he was trying to do with the test, and he didn't know.
I think it would be enormously valuable to teach most students what statistics means, what it can do, and what it can't do. I'm not sure how valuable it would be to teach everyone how to evaluate a big pile of magic statistical functions.