Surface plasmon polaritons (SPPs) are responsible for exotic optical phenomena, including negative refraction, surface enhanced Raman scattering, and nanoscale focusing of light. Although many materials support SPPs, the choice of metal for most applications has been based on traditional plasmonic materials (Ag, Au) because there have been no side-by-side comparisons of the different materials on well-defined, nanostructured surfaces. Here, we report a platform that not only enabled rapid screening of a wide range of metals under different excitation conditions and dielectric environments, but also identified new and unexpected materials for biosensing applications. Nanopyramidal gratings were used to generate plasmon dispersion diagrams for Al, Ag, Au, Cu, and Pd. Surprisingly, the SPP coupling efficiencies of Cu and Al exceeded widely used plasmonic materials under certain excitation conditions. Furthermore, grazing angle excitation led to the highest refractive index sensitivities (figure of merit >85) reported at optical frequencies because of extremely narrow SPP resonances (full-width-at-half-minimum <6 nm or 7 meV). Finally, our screening process revealed that Ag, with the highest sensitivity, was not necessarily the preferred material for detecting molecules. We discovered that Au and even Pd, a weak plasmonic material, showed comparable index shifts on formation of a protein monolayer.