We study the phase stability, mechanical properties, and electronic structure of two ceramic systems, Ti1-xScxN and Ti1-xYxN, using first principles methods. Owing to the similarity in ionic radii and electronegativities of Ti and Sc, exothermic mixing is predicted in Ti1-xScxN, with four ordered intermetallic phases lying on the convex hull: TiScN2, TiSc8N9, TiSc9N10, and Ti3Sc2N5. These structures form layered rocksalt-type configurations displaying enhanced hardness due to strong d-p hybridization. In contrast, Ti1-xYxN exhibits endothermic mixing resulting from the mismatched properties of Ti and Y. We report phase diagrams for each system, showing Ti3Sc2N5 to be stable throughout a wide range of temperatures and concentrations. This compound achieves a hardness of 27.3 GPa, which is higher than the end members TiN and ScN, making it suitable for hard coatings. Our analysis reveals high hardness to be attributed to increased 3d eg occupation, decreased 3d t2g occupation, and low volume. NSF funded.