When public sector challenges are manifold, the citizens act as an important source of performance feedback on government practices. In this article, we explore current public sector challenges as perceived by citizens of five countries (n = 4,182)—Austria, Denmark, Germany, the Netherlands, and New Zealand. We analyze to what extent citizens rate a list of public sector topics as major challenges for the public sector as a whole, and for cities and municipalities. The findings indicate that citizens from all five countries are concerned about high-quality public infrastructure and an efficient and effective public service provision. However, some differences regarding the rating of public sector challenges were identified among the countries. For example, Danish citizens score transparency about public performance substantially less challenging than citizens of other countries. Based on a detailed discussion of our findings, we provide directions for (comparative) public administration research and policy development.