Maybe something based on orders of magnitude could be interesting? complete a city with <10 streets, get a level 1 badge, complete a city with <100 for level 2, etc. This would be a good incentive to do something with the long tail of low-completion cities most striders seem to have, and the badges could also be displayed on the user card for extra street cred.
Edit: since this has been split into its own topic I wanted to add that the badge on the name card for completing a city is the main idea. It would be cool to see who has already completed cities without having to dig into their profile, and having different tiers would also show the difficulty of the projects.