Why quantum mechanics? Imagine you're teaching a first course on quantum mechanics in which your students are well-versed in classical mechanics, but have never seen any quantum before.  How would you motivate the subject and convince your students that in fact classical mechanics cannot explain the real world and that quantum mechanics, given your knowledge of classical mechanics, is the most obvious alternative to try?
If you sit down and think about it, the idea that the state of a system, instead of being specified by the finitely many particles' position and momentum, is now described by an element of some abstract (rigged) Hilbert space and that the observables correspond to self-adjoint operators on the space of states is not at all obvious.  Why should this be the case, or at least, why might we expect this to be the case? 
Then there is the issue of measurement which is even more difficult to motivate.  In the usual formulation of quantum mechanics, we assume that, given a state $|\psi \rangle$ and an observable $A$, the probability of measuring a value between $a$ and $a+da$ is given by $|\langle a|\psi \rangle |^2da$ (and furthermore, if $a$ is not an eigenvalue of $A$, then the probability of measuring a value in this interval is $0$).  How would you convince your students that this had to be the case?
I have thought about this question of motivation for a couple of years now, and so far, the only answers I've come up with are incomplete, not entirely satisfactory, and seem to be much more non-trivial than I feel they should be.  So, what do you guys think?  Can you motivate the usual formulation of quantum mechanics using only classical mechanics and minimal appeal to experimental results?
Note that, at some point, you will have to make reference to experiment.  After all, this is the reason why we needed to develop quantum mechanics.  In principle, we could just say "The Born Rule is true because its experimentally verified.", but I find this particularly unsatisfying.  I think we can do better.  Thus, I would ask that when you do invoke the results of an experiment, you do so to only justify fundamental truths, by which I mean something that can not itself just be explained in terms of more theory.  You might say that my conjecture is that the Born Rule is not a fundamental truth in this sense, but can instead be explained by more fundamental theory, which itself is justified via experiment.
Edit:  To clarify, I will try to make use of a much simpler example.  In an ideal gas, if you fix the volume, then the temperature is proportional to pressure.  So we may ask "Why?".  You could say "Well, because experiment.", or alternatively you could say "It is a trivial corollary of the ideal gas law.".  If you choose the latter, you can then ask why that is true.  Once again, you can just say "Because experiment." or you could try to prove it using more fundamental physical truths (using the kinetic theory of gases, for example).  The objective, then, is to come up with the most fundamental physical truths, prove everything else we know in terms of those, and then verify the fundamental physical truths via experiment.  And in this particular case, the objective is to do this with quantum mechanics.
 A: I am late to this party here, but I can maybe advertize something pretty close to a derivation of quantum mechanics from pairing classical mechanics with its natural mathematical context, namely with Lie theory. I haven't had a chance yet to try the following on first-year students, but I am pretty confident that with just a tad more pedagogical guidance thrown in as need be, the following should make for a rather satisfactory motivation for any student with a little bit of mathematical/theoretical physics inclination.
For more along the following lines see at nLab:quantization.

Quantization of course was and is motivated by experiment, hence by observation of the observable universe: it just so happens that quantum mechanics and quantum field theory correctly account for experimental observations, where classical mechanics and classical field theory gives no answer or incorrect answers. A historically important example is the phenomenon called the “ultraviolet catastrophe”, a paradox predicted by classical statistical mechanics which is not observed in nature, and which is corrected by quantum mechanics.
But one may also ask, independently of experimental input, if there are good formal mathematical reasons and motivations to pass from classical mechanics to quantum mechanics. Could one have been led to quantum mechanics by just pondering the mathematical formalism of classical mechanics? (Hence more precisely: is there a natural Synthetic Quantum Field Theory?)
The following spells out an argument to this extent. It will work for readers with a background in modern mathematics, notably in Lie theory, and with an understanding of the formalization of classical/prequantum mechanics in terms of symplectic geometry.
So to briefly recall, a system of classical mechanics/prequantum mechanics is a phase space, formalized as a symplectic manifold $(X,ω)$. A symplectic manifold is in particular a Poisson manifold, which means that the algebra of functions on phase space $X$, hence the algebra of classical observables, is canonically equipped with a compatible Lie bracket: the Poisson bracket. This Lie bracket is what controls dynamics in classical mechanics. For instance if $H\in C^{∞}(X)$ is the function on phase space which is interpreted as assigning to each configuration of the system its energy – the Hamiltonian function – then the Poisson bracket with $H$ yields the infinitesimal time evolution of the system: the differential equation famous as Hamilton's equations.
To take notice of here is the infinitesimal nature of the Poisson bracket. Generally, whenever one has a Lie algebra $\mathfrak{g}$, then it is to be regarded as the infinitesimal approximation to a globally defined object, the corresponding Lie group (or generally smooth group) $G$. One also says that $G$ is a Lie integration of $\mathfrak{g}$ and that $\mathfrak{g}$ is the Lie differentiation of $G$.
Therefore a natural question to ask is: Since the observables in classical mechanics form a Lie algebra under Poisson bracket, what then is the corresponding Lie group?
The answer to this is of course “well known” in the literature, in the sense that there are relevant monographs which state the answer. But, maybe surprisingly, the answer to this question is not (at time of this writing) a widely advertized fact that would have found its way into the basic educational textbooks. The answer is that this Lie group which integrates the Poisson bracket is the “quantomorphism group”, an object that seamlessly leads over to the quantum mechanics of the system.
Before we say this in more detail, we need a brief technical aside: of course Lie integration is not quite unique. There may be different global Lie group objects with the same Lie algebra.
The simplest example of this is already the one of central importance for the issue of quantization, namely the Lie integration of the abelian line Lie algebra $\mathbb{R}$. This has essentially two different Lie groups associated with it: the simply connected translation group, which is just $\mathbb{R}$ itself again, equipped with its canonical additive abelian group structure, and the discrete quotient of this by the group of integers, which is the circle group
$$
  U(1) = \mathbb{R}/\mathbb{Z}
  \,.
$$
Notice that it is the discrete and hence “quantized” nature of the integers that makes the real line become a circle here. This is not entirely a coincidence of terminology, but can be traced back to be at the heart of what is “quantized” about quantum mechanics.
Namely one finds that the Poisson bracket Lie algebra $\mathfrak{poiss}(X,ω)$ of the classical observables on phase space is (for X a connected manifold) a Lie algebra extension of the Lie algebra $\mathfrak{ham}(X)$ of Hamiltonian vector fields on $X$ by the line Lie algebra:
$$
  \mathbb{R} \longrightarrow \mathfrak{poiss}(X,\omega) \longrightarrow \mathfrak{ham}(X)
  \,.
$$
This means that under Lie integration the Poisson bracket turns into a central extension of the group of Hamiltonian symplectomorphisms of $(X,ω)$. And either it is the fairly trivial non-compact extension by $\mathbb{R}$, or it is the interesting central extension by the circle group $U(1)$. For this non-trivial Lie integration to exist, $(X,ω)$ needs to satisfy a quantization condition which says that it admits a prequantum line bundle. If so, then this $U(1)$-central extension of the group $Ham(X,\omega)$ of Hamiltonian symplectomorphisms exists and is called… the quantomorphism group $QuantMorph(X,\omega)$:
$$
  U(1) \longrightarrow QuantMorph(X,\omega) \longrightarrow Ham(X,\omega)
  \,.
$$
While important, for some reason this group is not very well known. Which is striking, because there is a small subgroup of it which is famous in quantum mechanics: the Heisenberg group.
More exactly, whenever $(X,\omega)$ itself has a compatible group structure, notably if $(X,\omega)$ is just a symplectic vector space (regarded as a group under addition of vectors), then we may ask for the subgroup of the quantomorphism group which covers the (left) action of phase space $(X,\omega)$ on itself. This is the corresponding Heisenberg group $Heis(X,\omega)$, which in turn is a $U(1)$-central extension of the group $X$ itself:
$$
  U(1) \longrightarrow Heis(X,\omega) \longrightarrow X
  \,.
$$
At this point it is worthwhile to pause for a second and note how the hallmark of quantum mechanics has appeared as if out of nowhere from just applying Lie integration to the Lie algebraic structures in classical mechanics:
if we think of Lie integrating $\mathbb{R}$ to the interesting circle group $U(1)$ instead of to the uninteresting translation group $\mathbb{R}$, then the name of its canonical basis element 1∈ℝ is canonically ”i”, the imaginary unit. Therefore one often writes the above central extension instead as follows:
$$
  i \mathbb{R} \longrightarrow \mathfrak{poiss}(X,\omega) \longrightarrow \mathfrak{ham}(X,\omega)
$$
in order to amplify this. But now consider the simple special case where $(X,\omega)=(\mathbb{R}^{2},dp∧dq)$ is the 2-dimensional symplectic vector space which is for instance the phase space of the particle propagating on the line. Then a canonical set of generators for the corresponding Poisson bracket Lie algebra consists of the linear functions p and q of classical mechanics textbook fame, together with the constant function. Under the above Lie theoretic identification, this constant function is the canonical basis element of $i\mathbb{R}$, hence purely Lie theoretically it is to be called ”i”.
With this notation then the Poisson bracket, written in the form that makes its Lie integration manifest, indeed reads
$$
  [q,p] = i
  \,.
$$
Since the choice of basis element of $i\mathbb{R}$ is arbitrary, we may rescale here the i by any non-vanishing real number without changing this statement. If we write ”ℏ” for this element, then the Poisson bracket instead reads
$$
  [q,p] = i \hbar
  \,.
$$
This is of course the hallmark equation for quantum physics, if we interpret ℏ here indeed as Planck's constant. We see it arise here by nothing but considering the non-trivial (the interesting, the non-simply connected) Lie integration of the Poisson bracket.
This is only the beginning of the story of quantization, naturally understood and indeed “derived” from applying Lie theory to classical mechanics. From here the story continues. It is called the story of geometric quantization. We close this motivation section here by some brief outlook.
The quantomorphism group which is the non-trivial Lie integration of the Poisson bracket is naturally constructed as follows: given the symplectic form $ω$, it is natural to ask if it is the curvature 2-form of a $U(1)$-principal connection $∇$ on complex line bundle $L$ over $X$ (this is directly analogous to Dirac charge quantization when instead of a symplectic form on phase space we consider the the field strength 2-form of electromagnetism on spacetime). If so, such a connection $(L,∇)$ is called a prequantum line bundle of the phase space $(X,ω)$. The quantomorphism group is simply the automorphism group of the prequantum line bundle, covering diffeomorphisms of the phase space (the Hamiltonian symplectomorphisms mentioned above).
As such, the quantomorphism group naturally acts on the space of sections of $L$. Such a section is like a wavefunction, instead that it depends on all of phase space, instead of just on the “canonical coordinates”. For purely abstract mathematical reasons (which we won’t discuss here, but see at motivic quantization for more) it is indeed natural to choose a “polarization” of phase space into canonical coordinates and canonical momenta and consider only those sections of the prequantum line bundle which depend on just the former. These are the actual wavefunctions of quantum mechanics, hence the quantum states. And the subgroup of the quantomorphism group which preserves these polarized sections is the group of exponentiated quantum observables. For instance in the simple case mentioned before where $(X,ω)$ is the 2-dimensional symplectic vector space, this is the Heisenberg group with its famous action by multiplication and differentiation operators on the space of complex-valued functions on the real line.

For more along these lines see at nLab:quantization.
A: All the key parts of quantum mechanics may be found in classical physics. 
1) In statistical mechanics the system is also described by a distribution function. No definite coordinates, no definite momenta. 
2) Hamilton made his formalism for classical mechanics. His ideas were pretty much in line with ideas which were put into modern quantum mechanics long before any experiments: he tried to make physics as geometrical as possible. 
3) From Lie algebras people knew that the translation operator has something to do with the derivative. From momentum conservation people knew that translations have something to do with momentum. It was not that strange to associate momentum with the derivative.
Now you should just mix everything: merge statistical mechanics with the Hamiltonian formalism and add the key ingredient which was obvious to radio-physicists: that you can not have a short (i.e, localized) signal with a narrow spectrum. 
Voila, you have quantum mechanics. 
In principle, for your purposes, Feynman's approach to quantum mechanics may be more "clear". It was found long after the other two approaches, and is much less productive for the simple problems people usually consider while studying. That's why it is not that popular for starters. However, it might be simpler from the philosophical point of view. And we all know that it is equivalent to the other approaches. 
A: As an initial aside, there is nothing uniquely ‘quantum’ about non commuting operators or formulating mechanics in a Hilbert space as demonstrated by Koopman–von Neumann mechanics, and there is nothing uniquely ‘classical’ about a phase space coordinate representation of mechanics as shown by Groenewold and Moyal’s formulation of Quantum theory. 
There does of course however exist a fundamental difference between quantum and classical theories. There are many ways of attempting to distil this difference, whether it is seen as non-locality, uncertainty or the measurement problem, the best way of isolating what distinguishes them that I have heard is this:
Quantum mechanics is about how probability phase and probability amplitude interact. This is what is fundamentally lacking in Hilbert space formulations of classical mechanics, where the phase and amplitude evolution equations are fully decoupled. It is this phase-amplitude interaction that gives us the wave-particle behaviour, electron diffraction in the two slits experiment, and hence an easy motivation for (and probably the most common entry route into) quantum mechanics. This phase-amplitude interaction is also fundamental to understanding canonically conjugate variables and the uncertainty problem. 
I think that if this approach were to be taken, the necessity of a different physical theory can be most easily initially justified by single-particle interference, which then leads on to the previously mentioned points.
A: Why would you ever try to motivate a physical theory without appealing to experimental results??? The motivation of quantum mechanics is that it explains experimental results. It is obvious that you would choose a simpler, more intuitive picture than quantum mechanics if you weren't interested in predicting anything.
If you are willing to permit some minimal physical input, then how about this: take the uncertainty principle as a postulate. Then you know that the effect on a system of doing measurement $A$ first, then measurement $B$, is different from doing $B$ first then $A$. That can be written down symbolically as $AB \neq BA$ or even $[A,B] \neq 0$. What kind of objects don't obey commutative multiplication? Linear operators acting on vectors! It follows that observables are operators and "systems" are somehow vectors. The notion of "state" is a bit more sophisticated and doesn't really follow without reference to measurement outcomes (which ultimately needs the Born rule). You could also argue that this effect must vanish in the classical limit, so then you must have $[A,B] \sim \hbar $, where $\hbar$ is some as-yet (and never-to-be, if you refuse to do experiments) undetermined number that must be small compared to everyday units. I believe this is similar to the original reasoning behind Heisenberg's matrix formulation of QM. 
The problem is that this isn't physics, you don't know how to predict anything without the Born rule. And as far as I know there is no theoretical derivation of the Born rule, it is justified experimentally! 
If you want a foundations viewpoint on why QM rather than something else, try looking into generalised probabilistic theories, e.g. this paper. But I warn you, these provide neither a complete, simple nor trivial justification for the QM postulates.
A: This is a late in coming relevant comment to the teaching problem you have (but not answer - I tried commenting but it was getting too big). 
Something you might mention in your class is modern control systems theory as taught to engineering students. I came to QM after I had studied control systems and practiced it in my job for a number of years and there is a natural feel to QM after this. Now I wonder whether QM might not have influenced the formulation of control systems theory. But basically one has a state space - the linear space of the minimum data one needs to uniquely define the system's future, a Schrödinger like evolution equation and observables that operate on the state and thus gather data for the feedback controller. The interpretation of the observables is radically different from how it's done in QM, however. But "evolving state + measurements" is the summary and even so, uncertainties in the observables leads to whole nontrivial fields of stochastic control systems and robust control systems (those that work even notwithstanding uncertainties in the mathematical models used). The engineering viewpoint also is very experimental - you seek to model your system accurately but you very deliberately don't give a fig how that model arises unless the physics can help you tune a model - but often the problems are so drenched with uncertainty that its just no help at all to probe the physics deeply and indeed control systems theory is about dealing with uncertainty, reacting to it and steering your system on a safe course even though uncertain outside uncontrollable forces buffet it endlessly. There are even shades of the uncertainty principle here: if your state model is uncertain and being estimated (e.g. by a Kalman filter), what your controller does will disturb the system you are trying to measure - although of course this the observer effect and not the Heisenberg principle, one does indeed find oneself trying to minimise the product of two uncertainties. You are wrestling with the tradeoff between the need to act against the need to measure.
This story won't fully motivate the subject in the way you want but it would still be interesting to show that there are a whole group of engineers and mathematicians who think this way and indeed find it very natural and unmysterious even when they first learn it. I think a crucial point here is that no-one frightens students of control theory before they begin with talk of catastrophic failure of theory, the need to wholly reinvent a field of knowledge and intellectual struggles that floored the world's best minds for decades. Of course in physics you have to teach why people went this way, but it's also important to stress that these same great minds who were floored by the subject have smoothed the way for us, so that now we stand on their shoulders and really can see better even though we may be far from their intellectual equals.
A: So far as I understand, you are asking for a minimalist approach to quantum mechanics which would motivate its study with little reference to experiments.
The bad. So far as I know, there is not a single experiment or theoretical concept that can motivate your students about the need to introduce Dirac kets $|\Psi\rangle$, operators, Hilbert spaces, the Schrödinger equation... all at once. There are two reasons for this and both are related. First, the ordinary wavefunction or Dirac formulation of quantum mechanics is too different from classical mechanics. Second, the ordinary formulation was developed in pieces by many different authors who tried to explain the results of different experiments --many authors won a Nobel prize for the development of quantum mechanics--. This explains why "for a couple of years now", the only answers you have come up with are "incomplete, not entirely satisfactory".
The good. I believe that one can mostly satisfy your requirements by using the modern Wigner & Moyal formulation of quantum mechanics, because this formulation avoids kets, operators, Hilbert spaces, the Schrödinger equation... In this modern formulation, the relation between the classical (left) and the quantum (right) mechanics axioms are
$$A(p,x) \rho(p,x) = A \rho(p,x)
~~\Longleftrightarrow~~
A(p,x) \star \rho^\mathrm{W}(p,x) = A \rho^\mathrm{W}(p,x)$$
$$\frac{\partial \rho}{\partial t} = \{H, \rho\}
~~\Longleftrightarrow~~
\frac{\partial \rho^\mathrm{W}}{\partial t} = \{H, \rho^\mathrm{W}\}_\mathrm{MB}$$
$$\langle A \rangle = \int \mathrm{d}p \mathrm{d}x A(p,x) \rho(p,x)
~~\Longleftrightarrow~~
\langle A \rangle = \int \mathrm{d}p \mathrm{d}x A(p,x) \rho^\mathrm{W}(p,x)$$
where $\star$ is the Moyal star product, $\rho^\mathrm{W}$ the Wigner distribution and $\{ , \}_\mathrm{MB}$ the Moyal bracket. The functions $A(p,x)$ are the same than in classical mechanics. An example of the first quantum equation is $H \star \rho_E^\mathrm{W} = E \rho_E^\mathrm{W}$ which gives the energy eigenvalues.
Now the second part of your question. What is the minimal motivation for the introduction of the quantum expressions at the right? I think that it could be as follows. There are a number of experiments that suggest a dispersion relation $\Delta p \Delta x \geq \hbar/2$, which cannot be explained by classical mechanics. This experimental fact can be used as motivation for the substitution of the commutative phase space of classical mechanics by a non-commutative phase space. Mathematical analysis of the non-commutative geometry reveals that ordinary products in phase space have to be substituted by start products, the classical phase space state has to be substituted by one, $\rho^\mathrm{W}$, which is bounded to phase space regions larger than Planck length--, and Poisson brackets have to be substituted by Moyal brackets.
Although this minimalist approach cannot be obtained by using the ordinary wavefunction or Dirac formalism, there are three disadvantages with the Wigner & Moyal approach however. (i) The mathematical analysis is very far from trivial. The first quantum equation of above is easily derived by substituting the ordinary product by a start product and $\rho \rightarrow \rho^\mathrm{W}$ in the classical expression. The third quantum equation can be also obtained in this way, because it can be shown that
$$ \int \mathrm{d}p \mathrm{d}x A(p,x) \star \rho^\mathrm{W}(p,x) = \int \mathrm{d}p \mathrm{d}x A(p,x) \rho^\mathrm{W}(p,x)$$
A priori one could believe that the second quantum equation is obtained in the same way. This does not work and gives an incorrect equation. The correct quantum equation of motion requires the substitution of the whole Poisson bracket by a Moyal bracket. Of course, the Moyal bracket accounts for the non-commutativity of the phase space, but there is not justification for its presence in the equation of motion from non-commutativity alone. In fact, this quantum equation of motion was originally obtained from the Liouville Von Neuman equation via the formal correspondence between the phase space and the Hilbert space, and any modern presentation of the Wigner & Moyal formulation that I know justifies the form of the quantum equation of motion via this formal correspondence. (ii) The theory is backward incompatible with classical mechanics, because the commutative geometry is entirely replaced by a non-commutative one. As a consequence, no $\rho^\mathrm{W}$ can represent a pure classical state --a point in phase space--. Notice that this incompatibility is also present in the ordinary formulations of quantum mechanics --for instance no wavefunction can describe a pure classical state completely--. (iii) The introduction of spin in the Wigner & Moyal formalism is somewhat artificial and still under active development.
The best? The above three disadvantages can be eliminated in a new phase space formalism which provides a 'minimalistic' approach to quantum mechanics by an improvement over geometrical quantisation. This is my own work and details and links will be disclosed in the comments or in a separated answer only if they are required by the community.
A: There's no one best way to answer the question "Why quantum mechanics?", because the best answer will depend on exactly what the questioner is skeptical about. Suppose that the local chapter of the Quantum Mechanics Haters' Union (QMHU) invited me to defend the concept to them.
First Alice says, "I don't really know anything about QM, but I've heard that it uses 'probability clouds' and 'many worlds' and 'nothing is true' and stuff, and I just can't bring myself to believe that something so weird could be right." I would explain the phenomenon of single-electron double-slit interference to her. It's pretty obvious that no theory of classical point particles can explain that.
Then Bob says, "I have a solid undergraduate or graduate background in QM, and I admit that single-electron double-slit interference is really weird. But quantum mechanics seems even weirder, so I still bet that there's some totally classical explanation for it." I would explain the Kochen-Specker and Bell's theorems to him.
Then Charlie says, "Okay, you've persuaded me that classical mechanics can't explain things like single-electron double-slit interference. But it's not obvious that quantum mechanics can either. After all, that's actually a pretty tricky system to analyze quantitatively." I would explain the energy spectra of the hydrogen atom to him, and show that one calculation that only takes a few lectures to go through can predict real observed phenomena extremely accurately.
Then Deborah says, "Okay, that's pretty impressive. But I bet without too much effort, we could come up with a more straightforward theory that makes equally quantitatively accurate predictions." I would explain to her that the theoretically predicted and experimentally measured values of the anomalous magnetic moment of the electron agree to ten significant figures, and that no prediction in any realm of human existence has ever been that quantitatively accurate - so any alternative to QM would need to be pretty dang good.
Then Ethan says, "Okay, I'm convinced that QM is very useful for explaining some weird things that happen when you shoot an electron at two narrow slits, or precisely measure the frequency of light emitted by electrically excited hydrogen. But who cares? I've never done any of those things and I never will." I would explain to him that quantum mechanics is crucial for understanding how to create a wide range of useful materials - most notably semiconductors, which pretty much all electronic equipment made in the past 50 years relies on.
Then Franny says, "My objection is the same as Ethan's, except I'm Amish so I don't use electronics, and your answer to him doesn't satisfy me." I would explain to her that the Pauli exclusion principle - which only makes sense for quantum systems - is what keeps the electrons in every atom in her body in their orbitals and prevents them all from crashing down into the $1s$ state, which would cause her to melt into a bosonic puddle.
Then George says, "I'm a philosophy professor, so I don't care about anything remotely practical or important. All I care about is 'big questions'." I would explain to him that the development of quantum mechanics is one of the events in all of human history that has most radically changed our understanding of the basic ontological nature of existence, and that philosophers are still actively debating what it "really means."
Then Harriett says, "Same as George, but I'm a math professor so all I care about is math." I would explain to her that the development of QM has led to huge, Fields-medal-winning developments in our understanding of pure math, like in the areas of fiber bundles, quantum field theory, and topological field theory.
Then Iris says, "I don't care about any of that stuff. All I want is lots and lots of money." I would explain to her that relatively soon, quantum computers may be able to efficiently factor large numbers, breaking the RSA encryption scheme which is used by most banks - so if she gets her hands on one, she might be able to steal lots and lots of money.
Then Jonathan Gleason says "I have no personal objection to the idea of quantum mechanics, I just find it very hard to wrap my head around. Can you give me a five-sentence conceptual summary, assuming a solid understanding of classical mechanics?" (See what I did there? I think this question is the closest to the OP's original formulation.) This is how I would answer: "Classical mechanics is pretty harsh about not allowing any functional variation $\delta S / \delta \varphi$ at all in the action. Everyone makes mistakes - no need to throw the book at those fields. Instead of completely prohibiting any field configuration for which the action is changing even a tiny bit, let's be nice. We'll let the fields get away with occasionally taking on some values at which the action isn't completely stationary. But we don't want those dang fields abusing our liberal attitudes, so we'll penalize them on a sliding scale, where the more rapidly the action is changing at a particular field configuration, the more we put our foot down."
A: It seems to me your question is essentially asking for a Platonic mathematical model of physics, underlying principles from which the quantum formalism could be justified and in effect derived. If so, that puts you in the minority (but growing) realist physicist camp as opposed to the vast majority of traditional instrumentalists.
The snag is the best if not only chance of developing a model like that requires either God-like knowledge or at least, with almost superhuman intuition, a correct guess at the underlying phenomena, and obviously nobody has yet achieved either sufficient to unify all of physics under a single rubrik along those lines.
In other words, ironically, to get at the most abstract explanation requires the most practical approach, rather as seeing at the smallest scales needs the largest microscope, such as the LHC, or Sherlock Holmes can arrive at the most unexpected conclusion only with sufficient data (Facts, Watson, I need more facts!)
So, despite being a fellow realist, I do see that instrumentalism (being content to model effects without seeking root causes, what might be compared with "black box testing") has been and remains indispensable.
A: I always like to read "BERTLMANN'S SOCKS AND THE NATURE OF REALITY" * by J. Bell to remind myself when and why a classical description must fail.
He basically refers to the EPR-correlations. You could motivate his reasoning by comparing common set theory (e.g. try three different sets: A,B,C and try to merge them somehow) with the same concept of "sets" in Hilbert spaces and you will see that they are not equal (Bell's theorem).


*

*http://hal.archives-ouvertes.fr/jpa-00220688/en/
A: Thomas's Calculus has an instructive Newtonian Mechanics exercise which everyone ought to ponder: the gravitational field strength inside the Earth is proportional to the distance from the centre, and so is zero at the centre.  And, of course, there is the rigorous proof that if the matter is uniformly distributed in a sphere, then outside the sphere it exerts a gravitational force identical to what would have been exerted if all the mass had been concentrated at the centre.
Now if one ponders this from a physical point of view, «what is matter», one ends up with logical and physical difficulties that were only answered by de Broglie and Schroedinger's theory of matter waves.  
This also grows out of pondering Dirac's wise remark: if «big» and «small» are mereley relative terms, there is no use in explaining the big in terms of the small...there must be an absolute meaning to size.  
Is matter a powder or fluid that is evenly and continuously distributed and can take on any density (short of infinity)? Then that sphere of uniformly distributed matter must shrink to a point of infinite density in a finite amount of time.... Why should matter be rigid and incompressible? Really, this is inexplicable without the wave theory of matter.  Schroedinger's equation shows that if, for some reason, a matter wave starts to compress, then it experiences a restoring force to oppose the compression, so that it can not proceed past a certain point (without pouring more energy into it).
See the related https://physics.stackexchange.com/a/18421/6432 .  Only this can explain why the concept of «particle» can have some validity and not need something smaller still to explain it.
A: In his Principles of Quantum Mechanics, Dirac outlines some inherent theoretical issues with classical mechanics that might motivate some to take some of the basic tenets of quantum mechanics as anticipated fundamental features of physics without reference to the actual experiments that led to the precise version of quantum mechanics as we understand it today. Of course, Dirac also outlines the experimental failures of classical mechanics in the same chapter in which he mentions these theoretical considerations (in fact, he mentions the experimental failures prior to the theoretical considerations--probably for the obvious reason that nobody would like to take the rather vague theoretical concerns with such a successful scheme of classical mechanics very seriously until they are faced with the brute fact that the scheme is indeed not generically adequate). With this preface, for what it's worth, here are the theoretical considerations that Dirac put forward:  
If we want to explain the ultimate structure of matter then it cannot be understood in the classical way of thinking. Because the classical approach would be to understand the macroscopic matter in terms of its microscopic constituents. But the issue is "To what end?". Clearly, classically, one would imagine that these microscopic constituents are further made up of even more microscopic constituents. (And if you think about it, this really adds up a lot of structure (information if you wish) to matter that cannot be accounted for when we measure the finite specific heat capacities of matter. So explaining the big in the terms of the small cannot be successful until we know where to stop. And there cannot be a logical stopping point unless we have an absolute meaning to the small. The only generic notion of big and small can be defined in reference to the disturbance that a measurement causes to the system. Since the classical thought suggests that the measurements can be as gentle as we want, there is no absolute small because, for a gentle enough measurement, any system can be thought of as sufficiently big. The only way out is that there be a limit to how gentle the measurements can in principle be--for this will facilitate the notion of an absolute small scale. The scale at which constituents can be truly treated as structureless with no further internal structure. Once we have gotten this far, we can further assert that since certain measurements are necessarily ungentle to a certain extent, the outcome of those measurements cannot causally follow from the previous state of the system which--by assumption--must get disturbed by the ungentleness of the measurement. 
So, we have got the inescapable uncertainty and the inevitability of the probabilistic nature of the outcomes of measurements. Of course, all of this is extremely hand-wavy stuff but since the OP asked for something purely theoretical, I thought this must be as far as one can go from purely theoretical considerations because that is how far Dirac went! 
PS: There is a very loose way to very partially motivating the path integral version of quantum mechanics from classical mechanics without reference to any other discussion of quantum mechanics. That is to take the action principle religiously seriously. That is to say that since the action principle seems to select out the whole trajectory at once out of all the other possible trajectories rather than figuring out the path in the step-motherly fashion of explicitly deterministic Newtonian law of motion if we are to elevate this distinctive feature of the action principle (for some mysterious reason) then we can say that the particle actually considers all the possible paths to go from a point to the other. This could possibly motivate one to actually think of the particle as in superposition of all these trajectories. The rest of the features still remain quite unclear tho. 
A: You should use history of physics to ask them questions where classical physics fail. For example, you can tell them result of Rutherford's experiment and ask: If an electron is orbiting around nucleus, it means a charge is in acceleration. So, electrons should release electromagnetic energy. If that's the case, electrons would loose its energy to collapse on Nucleus which would cease the existence of atom within a fraction of second (you can tell them to calculate). But, as we know, atoms have survived billions of years. How? Where's the catch?
A: If I would be designing an introduction to quantum physics course for physics undergrads, I would seriously consider starting from the observed Bell-GHZ violations. Something along the lines of David Mermin's approach. If there is one thing that makes clear that no form of classical physics can provide the deepest law of nature, this is it. (This does make reference to experimental facts, albeit more of a gedanken nature. As others have commented, some link to experiments is, and should be, unavoidable.)
A: Though there are many good answers here, I believe I can still contribute something which answers a small part of your question.
There is one reason to look for a theory beyond classical physics which is purely 
theoretical and this is the UV catastrophe. According to the classical theory of light, an ideal black body at thermal equilibrium will emit radiation with infinite power. This is a fundamental theoretical problem, and there is no need to appeal to any experimental results to understand it, a theory which predicts infinite emitted power is wrong.  
The quantization of light solves the problem, and historically this played a role in the development of quantum mechanics.
Of course this doesn't point to any of the modern postulates of quantum mechanics you're looking to justify, but I think it's still good to use the UV catastrophe as one of the motivations to look for a theory beyond classical physics in the first place, especially if you want to appeal as little as necessary to experimental results.
A: Classical mechanics is not final theory from the one side and is not further decomposable from the other. So you can't improve it, it is given as is. 
For example, you can't explain why if moving body is disappearing from previous point of it's trajectory it should reappear at infinitesimal close point but can't appear a meter ahead (teleporting). What does constraining trajectory points into continuous line? No answer. This is axiom. You can't build a MECHANISM for constraining.
Another example: you can't stop decomposing bodies into parts. You can't reach final elements (particles) and if you do, then you can't explain why these particles are indivisible anymore. The matter should be continuous in classics while you can't imagine how material points exist.
Also, you can't explain, how the entire infinite universe can exist simultaneously in it's whole information. What is happening in absolutely closed box or what is happening in absolute unreachable regions of spacetime? Classics tends us think that reality is real there too. But how it can be if it is absolutely undetectable? Scientific approach says that only what is measurable does exist. So how can it be reality in absolutely closed box (with cat in it)?
In classic mechanic you can't reach absolute identity of building blocks. For example, if all atoms are build of protons, neutrons and electrons, these particles are similar, but not the same. Two electrons in two different atoms are not the same in classic, they are two copies of one prototype, but not the prototype itself. So, you can't define really basic building blocks of reality in classics.
You can't define indeterminism in classics. You can't define unrealized possibilities in classic and can't say what have happened with possibility which was possible but not realized. 
You can't define nonlocality in classics. There are only two possibilities in classics: one event affects another (a cause and effect) and two events are independent. You can't imagine two events correlate but don't affect each other! This is possible but unimaginable in classics!
