Disclaimer: This is not really an answer, but rather a "long comment". However, I hope it can provide some useful insights. Anyway, I think that this question can be basically considered a duplicate of Is there a way to obtain the classical partition function from the quantum partition function in the limit $h→0$?.
The first version of the partition function you report,
$$\tag{1}\label{1} Z_{qm}=\sum_{\text{states}} e^{-\beta E_i}$$
is intrinsically quantum mechanical, and has little meaning in classical mechanics, unless you are considering some model system with a discrete number of states (like the Ising model).
Note that the index $i$ of \ref{1} must be interpreted as running over the states of the system, not over the energy levels. In quantum mechanics, the number of states of a system is in general discrete, and therefore an expression like \ref{1} is meaningful. You can transform it in a sum over the energy levels if you want, by writing
$$\tag{2}\label{2} Z_{qm} = \sum_{\text{energy levels}} g_i e^{-\beta E_i}$$
where $g_i$ is the degeneracy of the energy level $E_i$, i.e. the number of different quantum states corresponding to this energy level.
In classical mechanics, you have a continuum of states, which we call the phase space. Every point $P=(\mathbf x_1, \dots, \mathbf x_N,\mathbf q_1, \dots, \mathbf q_N)$ in phase space corresponds to a different physical state. Therefore an expression like \ref{1} has no meaning in classical physics. The corresponding classical expression is indeed
$$\tag{3}\label{3} Z_{cm} = \frac 1 {h^{3N} N!} \int e^{-\beta H (p,q)} d^N \mathbf p d^N \mathbf x$$
However, we know that classical mechanics is an approximation of quantum mechanics. Therefore, under some condition we must be able to approximate \ref{1} with \ref{2}:
$$Z_{qm} \approx Z_{cm}$$
To rigorously prove that we can do this approximation is quite cumbersome. In K. Huang, Statistical Mechanics, second edition paragraph 9.2 you can find a rigorous proof of this result for the case of non-interacting particles (ideal gas), but the general case is quite cumbersome.
You can find another proof in this article (there is a paywall, though), which also mainly considers an ideal gas.
Another, more simple derivation in the case of a single particle in 1D can be found on these lecture notes (par. 2.1.1).
I have been thinking about a way to explain the general idea of such approximation is simple terms without relying too much on quantum mechanical concepts, but I admit that I found no explanation that would not dumb down the concept excessively. In other words, I cannot provide you any explanation that wouldn't be a "lie", and the best suggestion that I can give you is to actually learn some quantum mechanics and then take a look at the derivation from one of the sources I cited.
In particular, I will note that even though a non quantum mechanical derivation can be attempted, you will never be able to get from it:
- The factor $h^{3N}$, which come from phase space quantization. In some sense, as also explained by knzhou in his answer, this come from the fact that a quantum state occupies approximately a volume $h$ in phase space.
- The factor $N!$, which comes from the indistinguishability of quantum particles. In purely classical mechanics, this factor must be put in Z by hand, to avoid double counting of stats which only differ by a permutation of identical particles. Notice that even if in classical mechanics particles are always distinguishable, they are still identical, i.e. the classical Hamiltonian remains unchanged if you exchange the label of two atoms. Because of this, you need the factor $N!$ in classical mechanics too. However, it comes form quantum indistinguishability.