Gravity makes molecules gradually accelerate downwards. Neglecting collisions, the molecules closer to the earth would thus be (on average) moving faster.
You cannot neglect collisions, at least not in the part of the atmosphere where the atmosphere acts like a gas. Collisions remain important until you get to the exobase. Above the exobase, the atmosphere is so rare that collisions can be ignored. Modeling the exosphere is messy because now you have to worry about solar flares, the Earth's magnetic field, and a varying distribution of components (e.g., the exosphere is dominated by hydrogen).
Collisions are extremely important in the thick part of the atmosphere (up to 120 km or so). At sea level, the mean free path (average distance between collisions) in the atmosphere is less than 1/10 of a micrometer. At 20 kilometers altitude, the mean free path is about one micrometer. By the time you get to 120 kilometers, the mean free path grows to about a meter. Collisions remain important until you get to the exobase.
Temperature in the atmosphere follows a complex profile. The highest temperatures are in the two highest layers of the atmosphere, the thermosphere and exosphere.
Your second argument suffers many of the same problems as your first. You cannot ignore collisions. Collisions are an essential part of what make a gas a gas. Things are a bit murky in the one part of the atmosphere, the exosphere, where collisions can be ignored. There is one easy way to model the exosphere: It's essentially a vacuum. Getting past that easy model is non-trivial. Even the thermosphere (the next layer down, where the space station orbits) is problematic to model. The atmosphere is still thin enough in the thermosphere that it doesn't act quite like a gas.
It's the mesosphere on down where the atmosphere acts like a gas. That the components are constant colliding with one another is what makes pressure in the lower atmosphere equal to the weight of all the stuff above. This isn't necessarily true in the upper atmosphere.
Yes, the temperature of a gas (either real or ideal) is lower at the top of a container. A simple example is Earth's atmosphere, which is colder at the top than at the bottom.
There's an obvious caveat: if the gas is in thermal equilibrium with its container, e.g. because the container is quite small or the pressure is quite high, then of course there can't be a temperature gradient.
The reason temperature varies with elevation is not quite what you came up with. I think your argument is valid within your definition of an ideal gas: the particles that climb high up in your box clearly have less kinetic energy than they did on the ground, so their temperature is reduced. (It helps your illustration to imagine that the box is 10 miles high and 10 feet wide.) But in the usual definitions, ideal gas molecules are small hard spheres, so their collisions induce scattering, which scrambles their speeds and directions. I think the effect of this scattering would be that the kinetic energy "lost" by a single particle as a result of rising up in the box would be refunded by collisions with other particles being scattered from below or above.
To show that the temperature of a gas decreases with increasing elevation, I reproduce a simplified version of the argument in Exercise 2042 from Doron Cohen's online stat-mech notes.
Consider a box of fixed volume in a gravitational field, containing an ideal gas that is not at thermal equilibrium. An arbitrarily thin "layer" of gas at the bottom of the box has pressure $P_0$, number density $n_0$, and temperature $T_0$, with $P_0=n_0T_0$ (eliding the gas constant for convenience). As some gas rises (or falls), it does adiabatic work on its surroundings, which changes the energy content of the rising (or falling) gas. Therefore, at every "layer" at height $h$ we have $$P(h)=Cn(h)^\gamma$$ where the constant is $C=T_0n_0^{1-\gamma}$ and $\gamma$ is another constant, the so-called adiabatic index.
The pressure must vary continuously up the box, which leads to the condition $$dP(h)=-mgn(h)\space dh$$
where $m$ is the mass of the particle and $g$ is the local acceleration due to gravity.
We have $P(h)=Cn(h)^\gamma$ from above, so $dP(h)=C\gamma n(h)^{\gamma-1} dn$. Integrating the continuity condition above with this definition of $dP$ brings us (eventually) to a final result,
$$n(h)=n_0\left(1-\frac{\gamma-1}\gamma \cdot \frac{mgh}{T_0}\right)$$
and since temperature is $T=P/n$, the height-dependent temperature is
$$T(h)=P(h)/n(h)=Cn(h)^{\gamma-1}=T_0-\left(\frac{\gamma-1}\gamma\right)mgh.$$
So we see that the pressure gradient induced by gravity produces a temperature gradient: the higher you go in the box, the colder the gas gets.
Best Answer
An atmosphere in absolute equilibrium in fact is isothermal (see below for more detailed analysis of your cannonball). However, if the atmosphere is mixed by wind, gas expands and contracts adiabatically. If the mixing is fast enough, it obeys relatively well the adiabatic invariant, which multiplied by suitable form of ideal gas law ($(T/(pV))^\gamma = 1/(\nu R)^\gamma = const$) results in
$$pV^\gamma = const \Rightarrow$$ $$\frac{T^\gamma}{p^{\gamma - 1}} = const $$
Thus, if the pressure decreases with altitude, temperature also decreases, assuming the air is adiabatic.
So, what about the cannonball?
Instead of cannonballs moving in 3d space, lets just consider 1d upwards shooting cannon. In your example, you made a slight mistake. Instead of shooting a single cannonball, you should have shot many and with velocities according to Bolzmann distribution - the probability of shooting some cannonball with velocity $v$ is proportional to $e^{-E/kT} = e^{-mv^2/2kT}$ (ideal gas obeys exactly the same probability relation). You correctly noticed that a cannonball at $h = 0$ has less kinetic energy at height $h = h'$, which led to your result. But you didn't take into account that only cannonballs with high enough initial energy can reach an altitude of $h'$, thus "filtering" out the low energy balls. This effect conversely increases the average energy of the cannonball - which happens to exactly compensate the effect mentioned above.
More mathematically - in order to get the distribution of velocities at some other height, let's first ask what is the probability of reaching a maximum altitude of $h_{max}$. From energy conservation, $mv_z^2/2 = mgh_{max}$ (only the $z$ component is important). Thus the probability is simply proportional to $e^{-mgh_{max}/kT}$. If we are sitting at height $h'$, the probability distribution for a cannonball to rising for another $\Delta h$ is $p \propto e^{-mgh_{max}/kT} \propto e^{-mgh_{max}/kT}e^{-mgh'/kt} = e^{-mg(h_{max} - h')/kT} = e^{-mg \Delta h/kT}$ (I just multiplied rhs by a constant factor). Keeping in mind that $mg \Delta h = mv'^2/2$ is also the kinetic energy at that height, we conclude that the velocity distribution and thus the average kinetic energy are the same at different heights.