The effect of crystallite size on cation coordination environments and oxygen vacancy ordering has been investigated in micro- and nanocrystalline Y- and Sc-doped ZrO2 and CeO2 by using high-resolution 89Y and 45Sc magic-angle-spinning nuclear magnetic resonance (MAS NMR) spectroscopy. Our results indicate that irrespective of crystallite size the vacancies are preferentially associated with the host cation (i.e., Zr) in Y-doped ZrO2 while they display a preference for the dopant cation (i.e., Sc) in Sc-doped ZrO2. On the other hand, vacancies prefer to be associated with the dopant cation in both Y- and Sc-doped CeO2. However, the reduction of crystallite size to a few nanometers shows an unexpected and remarkable effect of increasing randomness in the vacancy distribution in all materials. Such an effect is hypothesized to result from a higher degree of short-range structural disorder in the cation coordination environments in nanocrystals compared to that in their microcrystalline counterparts that controls the energetics of vacancy ordering via a complex balance between electrostatic and strain energy terms. Finally, a clear connection is established between vacancy ordering, oxygen ion transport, and electrical conductivity in microcrystalline Y-doped CeO2 and its possible implications on ionic transport in nanocrystalline materials are discussed.