Clouds are made up of very tiny liquid water droplets that have small fall speeds. This means that with just a little bit of upward velocity in the wind, the cloud water can remain aloft and appear to float. Clouds are not always static blobs -- if you watch some clouds you will see that air can flow through them, condensing into new cloud where it goes in and evaporating into clear air on its way out (easily visible in mountain wave clouds).
The reason clouds tend to have a consistent base altitude is due to how temperature and water vapor behave in the boundary layer. On sunny, windy days the boundary layer is well mixed and potential temperature and water vapor mixing ratio are constant with height. With a constant potential temperature the actual temperature will decrease at about 10$^\circ$C per kilometer of height. With constant specific humidity and decreasing temperature as we go upward this means the relative humidity is increasing. At some height the relative humidity becomes 100% and we call this height the lifted condensation level (LCL), which will also be the height of the cloud bases. If surface characteristics are similar across an area, so will be the LCL and this will make all the clouds in the area have similar bases. You were on the right track with the significant change in air composition, but it is a thermodynamic change with pressure playing a significant role.