List terms of custom taxonomy if matches other taxonomy

Your approach isn’t bad, but instead of echoing all of these out, you should store them in an array, then use array_unique to remove duplicate entries before displaying.

<?php 
$array_out = array();
while ($the_query->have_posts()) : $the_query->the_post(); ?>
    $terms = get_the_terms( $post->ID, 'city'); 
    foreach($terms as $term){
        $term_link = get_term_link($term, 'city');
        $array_out[] = '<a href="'.$term_link.'">'.$term->name.'</a>';
    }
endwhile; 

$array_clean = array_unique($array_out);
echo '<p>' . implode('</p><p>', $array_clean) . '</p>';

We have to build the link ourselves using get_term_link() so the array holds each term separately, not by group as it is related to each post.