Oxide electrolytes find use in a wide range of technologies, from traditional areas of solid oxide fuel cells and electrochemical sensors, to new applications in solid state batteries and memristors. Ionic transport in these oxides has traditionally been exploited and studied at high temperatures at which ion motion is facile. The newer applications, however, require new materials suitable for near ambient temperatures operation, at which not only bulk but also interfacial transport becomes important. Here, we address both the understanding and discovery of oxide electrolytes using advanced experimental methods. First, we present the use of electron holography to characterize the internal boundaries in lightly doped CeO2, a canonical electrolyte material. We show that, consistent with traditional space charge models of ceria, the grain boundaries are positively charged, and that oxygen vacancy depletion in the space charge zone is likely responsible for the high impedance of grain boundaries. However, we find an enormous variability in potential as measured at different boundaries, which is accompanied by a similarly large variability in the grain boundary impurity content. Thus, although the overall impurity concentration is orders of magnitude lower than the dopant concentration, transport across the boundaries is apparently dominated by accidental impurities. Recognition of this origin of high grain boundary impedance provides a natural route for enhancing ionic conductivity at ambient temperatures. Second, we present a high throughput approach for developing new electrolytes using libraries of compositional gradients. We discuss the experimental requirements for achieving meaningful results from this unique geometry in which a compositionally graded film is deposited onto a conductive substrate and position-resolved impedance is recorded. The approach allows for new insights from transport measurements carried out with exquisite composition control, while supporting material discovery over a wide composition space.