How can I let templates choose which stylesheets are enqueued?

Check the current template in your callback. This is a post meta field named _wp_page_template.

add_action("wp_enqueue_scripts", function() 
{
    // This stylesheet is used on *every* page
    wp_register_style("sitewide", get_template_directory_uri() . "/assets/sitewide.css");
    wp_enqueue_style("sitewide");

    if ( ! is_singular() )
        return;

    $template = get_post_meta( get_the_ID(), '_wp_page_template', TRUE );

    // now enqueue further stylesheets depending on the current template
});