Add an empty option in first position:
...
echo '<option value="">All locations</option>';
$query = new WP_Query( $args );
while ( $query->have_posts() ) : $query->the_post();
echo '<option value="' . get_the_ID() . '">' . get_the_title() . '</option>';
endwhile;
...