// First, register your taxonomy and set the slug argument of rewrite to shows:
register_taxonomy(
    'show_category',
    'show',
    array(
        'rewrite' => array( 'slug' => 'shows', 'with_front' => false ),
        // your other args...
    )
);

// Next, register your post type and set the slug to shows/%show_category%, and set has_archive argument to shows:
register_post_type(
    'show',
    array(
        'rewrite' => array( 'slug' => 'shows/%show_category%', 'with_front' => false ),
        'has_archive' => 'shows', // THIS IS IMPORTANT, otherwise archive would have wrong link
        // your other args...
    )
);

// Last, add a filter to post_type_link to substitute the show category in individual show permalinks:
function wbkn_custom_post_type_permalinks( $post_link, $post ) {
    if ( is_object( $post ) && $post->post_type == 'show' ) {
        $terms = wp_get_object_terms( $post->ID, 'show_category' );
        if( $terms ) {
            return str_replace( '%show_category%' , $terms[0]->slug , $post_link );
        }
    }
    return $post_link;
}
add_filter( 'post_type_link', 'wbkn_custom_post_type_permalinks', 1, 2 );