How-to exclude terms from the main query the most performant way?

You can set the taxonomy query for the main query using pre_get_posts:

add_action( 'pre_get_posts', 'my_exclude_terms_from_query' );
function my_exclude_terms_from_query( $query ) {
    if ( $query->is_main_query() /* && whatever else */ ) {
        $tax_query = array (
                array(
                    'taxonomy' => 'category',
                    'terms' => array( 'cat-slug' ),
                    'field' => 'slug',
                    'operator' => 'NOT IN',
                )
        );
        $query->set( 'tax_query', $tax_query );
    }
}

If tax_query is already set and you need to modify it instead, you can grab and then add to the $tax_query array.