We present a comparative study on the morphology and structural as well as magnetic properties of crystalline Fe$_3$O$_4$/NiO bilayers grown on both MgO(001) and SrTiO$_3$(001) substrates by reactive molecular beam epitaxy. These structures are investigated by means of x-ray photoelectron spectroscopy, low energy electron diffraction, x-ray reflectivity and diffraction as well as vibrating sample magnetometry. While the lattice mismatch of NiO grown on MgO(001) is only 0.8%, it is exposed to a lateral lattice mismatch of -6.9% if grown on SrTiO$_3$. In the case of Fe$_3$O$_4$, the misfit strain on MgO(001) and SrTiO$_3$(001) amounts to 0.3% and -7.5%, respectively. To clarify the relaxation process of the bilayer system, the film thicknesses of the magnetite and nickel oxide films have been varied between 5 and 20nm. While NiO films are well ordered on both substrates, Fe$_3$O$_4$ films grown on NiO/SrTiO$_3$ exhibit a higher surface roughness as well as lower structural ordering compared to films grown on NiO/MgO. Further, NiO films grow pseudomorphic in the investigated thickness range on MgO substrates without any indication of relaxation, whereas on SrTiO$_3$ the NiO films show strong strain relaxation. Fe$_3$O$_4$ films exhibit also strong relaxation even for films of 5nm thickness on both NiO/MgO as well as on NiO/SrTiO$_3$. The magnetite layers on both substrates show a fourfold magnetic in-plane anisotropy with magnetic easy axes pointing in $leftlangle100rightrangle$ directions. The coercive field is strongly enhanced for magnetite grown on NiO/SrTiO$_3$ due to higher density of structural defects, compared to magnetite grown on NiO/MgO.