Here's my solution:
Instead of using a custom DB query (bad), I'm using the built in orderby query to order posts by a meta_key. Then, i get the post_meta for that key and do the magic, as outlined above:
<?php
$args = array(
'post_type' => 'publications',
'order' => 'ASC',
'orderby' => 'meta_value',
'meta_key' => 'publication_medium',
'posts_per_page' => 20
);
query_posts( $args );
if ( have_posts() ) : ?>
<?php while ( have_posts() ) : the_post(); ?>
<header>
<?php $meta_value = get_post_meta( $post->ID, '_uepi_publication_medium', true );
if ( $meta_value != $current_value ) {
echo "<h1 class='post-title'>" . ucfirst( substr_replace( $meta_value, $meta_value . 's', 0 ) ) . "</h1>";
$current_value = $meta_value;
}
?>
</header>
<article>
<?php the_content(); ?>
</article>
<?php endwhile; endif; ?>