To achieve ambitious greenhouse gas emission reduction targets in time, the planning of future energy systems needs to accommodate societal preferences, e.g.~low levels of acceptance for transmission expansion or onshore wind turbines, and must also acknowledge the inherent uncertainties of technology cost projections. To date, however, many capacity expansion models lean heavily towards only minimising system cost and only studying few cost projections. Here, we address both criticisms in unison. While taking account of technology cost uncertainties, we apply methods from multi-objective optimisation to explore trade-offs in a fully renewable European electricity system between increasing system cost and extremising the use of individual technologies for generating, storing and transmitting electricity to build robust insights about what actions are viable within given cost ranges. We identify boundary conditions that must be met for cost-efficiency regardless of how cost developments will unfold; for instance, that some grid reinforcement and long-term storage alongside a significant amount of wind capacity appear essential. But, foremost, we reveal that near the cost-optimum a broad spectrum of regionally and technologically diverse options exists in any case, which allows policymakers to navigate around public acceptance issues. The analysis requires to manage many computationally demanding scenario runs efficiently, for which we leverage multi-fidelity surrogate modelling techniques using sparse polynomial chaos expansions and low-discrepancy sampling.