The modification of the properties of CeO$_2$ through aliovalent doping are investigated within the emph{ab-initio} density functional theory framework. Lattice parameters, dopant atomic radii, bulk moduli and thermal expansion coefficients of fluorite type Ce$_{1-x}$M$_{x}$O$_{2-y}$ (with M$ = $ Mg, V, Co, Cu, Zn, Nb, Ba, La, Sm, Gd, Yb, and Bi)are presented for dopant concentrations in the range $0.00 leq x leq 0.25$. The stability of the dopants is compared and discussed, and the influence of oxygen vacancies is investigated. It is shown that oxygen vacancies tend to increase the lattice parameter, and strongly decrease the bulk modulus. Defect formation energies are correlated with calculated crystal radii and covalent radii of the dopants, but are shown to present no simple trend. The previously observed inverse relation between the thermal expansion coefficient and the bulk modulus is shown to persist independent of the inclusion of charge compensating vacancies.