Ok, I figured it out! I was being way too complicated. Here’s the code I came up with, that works:
<?php
$wp_query = new WP_Query();
$wp_query->query(array(
'post_type'=>'location',
'paged' => $paged,
'orderby' => 'meta_value',
'meta_key' => 'city',
'order' => 'ASC'
));
$prev_city = ('');
while ($wp_query->have_posts()) : $wp_query->the_post();
$do_not_duplicate = $post->ID;
$city = $cfs->get('city');
if($prev_city != $city) echo '<h3>'.$city.'</h3>';
echo $cfs->get('practice_name');
$prev_city = $city;
endwhile;
wp_reset_postdata();
?>