I think that the relation between the Debye Temperature $\theta_D$ and the "hardness/softness" of the material can be understood more easily if we directly look at the expression for the Debye temperature itself:
\begin{equation}
\theta_D=\frac{\hbar \omega_{D}}{k_B}
\end{equation}
Here $\omega_D$ is the Debye frequency. This can be thought as the "maximum frequency the solid normal modes can stand". If we keep this in mind we can write:
\begin{equation}
\omega_D=\omega_{max}= v_s|\vec{k_{max}}|=\frac{2 \pi v_s}{\lambda_{min}}
\end{equation}
I've used the dispersion relation for sound waves ($v_s$ is the propagation velocity of sound in the solid) and then I replaced $k_{max}=\frac{2 \pi}{\lambda_{min}}$.
At this point we can already give a preliminar answer. Debye temperature is proportional to the sound velocity in the solid. If you google it you'll find something like this
Harder materials have higher sound velocities. This is because they are "tighter" and they propagate oscilations faster. So we indeed arrive to the conclusion that harder materials have higher Debye Temperatures.
If you don't buy this kind of empirical demostration, let's go a bit further. We still have a $\lambda_{min}$ in our definition of $\theta_D$ that haven't been used:
\begin{equation}
\theta_D=\frac{h v_s}{\lambda_{min}}
\end{equation}
In general, $\lambda_{min}$ will be related to the geometry of the material lattice. However, for our simple purposes we can simply say that $\lambda_{min}$ must be proportional to the average distante between ions in the lattice. This is easy to see: a wave with a smaller $\lambda$ simply doesn't have anywhing to oscilate in between the ions. So now we see that the Debye Temperature is also inversely proportional to the separation of ions in the lattice. It is obvious then that tighter lattices (with ions closer to each other) will have higher Debye Temperatures, in agreement with our first thoughts.
Hope this helps!
P.D.: answering the other question, harder materials usually have smaller heat capacities, not the other way around.