A novel surface involving ordered arrays of partially-embedded carbon nanotubes is developed theoretically. Analysis indicates it should exhibit ultra-low values for friction, adhesion and wear, and also possess superior thermal and electrical properties. The surface consists of orthogonally-oriented, self-assembling arrays of carbon nanotubes, partially embedded lengthwise in a solid substrate. Calculations indicate that stiction forces due to van der Waals interactions can be made small, perhaps more than an order of magnitude less than for Teflon and other advanced perfluorocarbons. Static and kinetic frictional forces could be three orders of magnitude less than for conventional solids.