Surface textures decrease friction in lubricated sliding contact with Newtonian lubricants. When using a non-Newtonian lubricant, the friction reduction is enhanced. In this study, we present a simultaneous design of the shape of a textured surface and the non-Newtonian viscometric functions using a multiobjective surrogate-based optimization technique. We model the flow of the non-Newtonian fluids between a flat plate and a texture surface using two different models: the Criminale-Ericksen-Filbey (CEF) model (which can be used to derive a modified Reynolds equation), and a multi-mode Giesekus model (which is used with the full 3-D Cauchy Momentum equations). We demonstrate the efficiency of our previously developed multiobjective adaptive surrogate modeling-based optimization (MO-ASMO) method, and provide insights into co-designing of the lubricant and textured surface, and how these results can be physically realized.