Dense, orientationally and translationally ordered, two-dimensional (2D) monolayers of colloidal ellipsoids are fabricated at air-water interfaces. Kinetic arrest and disordered structures from long-range quadrupolar capillary attraction are overcome by synthesizing polystyrene microellipsoids with surface roughness, specifically nanoscale concavities, which attenuate capillary attraction. With increasing area fraction, the particle assembly shows a disorder-order transition from isotropic to plastic crystal at low ellipsoid aspect ratio (AR) and an isotropic to nematic transition at high AR, agreeing qualitatively with simulated hard ellipse close-packing in 2D. The ordered particle assembly is successfully transferred to solid substrates via Langmuir-Blodgett deposition, demonstrating the potential of surface roughness to create anisotropically ordered 2D patterns via interfacial templating.