Deploying robots for public interest missions in a dynamic complex environment, such as a city, is technically and logistically challenging. Due to intended autonomy and coexistence with humans, the implementation also raises ethical and legal challenges. Although decisive for successful application and adoption, the ethical and legal challenges have yet to receive sufficient attention in the scientific and policy literature. It is also critical to assess the ramifications and overall impacts of service robots on sustainability, due to their production, use phase, and end of life. In this article, we set out to identify ethical, legal, and sustainability challenges when deploying service robots in and for cities. Our research is centered around the project “Robots and the City,” which took place in the city of Brussels, Belgium, and investigated how these service robots can aid in satisfying future potential needs in the delivery of public missions. We first describe key challenges identified along with research and stakeholders as well as measures to navigate them. We then emphasize the importance of integrating user perspectives to comply with ethical and legal standards. As a conclusion, we present an overview of the challenges of urban service robots and set up a list of recommendations for designers and developers. Finally, we discuss the impacts and feasibility of such measures.