We use perturbative Symanzik improvement to create a new staggered-quark action (HISQ) that has greatly reduced one-loop taste-exchange errors, no tree-level order a^2 errors, and no tree-level order (am)^4 errors to leading order in the quarks velocity v/c. We demonstrate with simulations that the resulting action has taste-exchange interactions that are at least 3--4 times smaller than the widely used ASQTAD action. We show how to estimate errors due to taste exchange by comparing ASQTAD and HISQ simulations, and demonstrate with simulations that such errors are no more than 1% when HISQ is used for light quarks at lattice spacings of 1/10 fm or less. The suppression of (am)^4 errors also makes HISQ the most accurate discretization currently available for simulating c quarks. We demonstrate this in a new analysis of the psi-eta_c mass splitting using the HISQ action on lattices where a m_c=0.43 and 0.66, with full-QCD gluon configurations (from MILC). We obtain a result of~111(5) MeV which compares well with experiment. We discuss applications of this formalism to D physics and present our first high-precision results for D_s mesons.