Adding a term name from a custom taxonomy assigned to a post link displayed by a wp_query loop based on another taxonomy

Something like this should help:

<?php
    $post_type="animals";
    $tax = 'vertebrate';

    $tax_terms = get_terms($tax);

    if ( $tax_terms ) {
        foreach ($tax_terms as $tax_term) {
            $args = array(
                'post_type' => $post_type,
                "$tax" => $tax_term->slug,
                'post_status' => 'publish',
                'posts_per_page' => -1,
                'caller_get_posts' => 1,
                'orderby' => 'title',
                'order' => 'ASC'                 
            );

            // $my_query = null;  <- REMOVE THIS, YOU DON'T NEED TO NULL VARIABLE BEFORE ASSIGNING IT'S VALUE

            $my_query = new WP_Query($args);
        ?>

            <?php if ( $my_query->have_posts() ) : ?>
                <h2><?php echo esc_html($tax_term->name); ?></h2>'; <?php // <- YOU SHOULD ESCAPE PRINTED VALUES ?>
                <ol>
                <?php while ($my_query->have_posts()) : ?>
                    $my_query->the_post(); ?>
                    <li>
                        <a href="https://wordpress.stackexchange.com/questions/158329/<?php the_permalink() ?>" rel="bookmark" title="Permanent Link to <?php the_title_attribute(); ?>"><?php the_title(); ?></a>
                        <?php 
                            // setup_postdata( $post ); <- THERE IS NO NEED TO SETUP_POSTDATA HERE (YOU'VE ALREADY CALLED the_post() ON QUERY
                            $type_terms = wp_get_post_terms( $post->ID, 'type');
                            if ( $type_terms ) {
                                echo '<span>('. esc_html($terms[0]->name) .')</span>';
                            }
                        ?>
                    </li>
                <?php endwhile; ?>
                </ol>
            <?php endif; ?>
        <?php
        // wp_reset_query(); <- YOU DON'T CHANGE GLOBAL $wp_query, SO THERE IS NO NEED TO RESET QUERY (ESPECIALLY DON'T DO THIS FOR EACH $tax_term
        }
    }
    // BUT YOU DO CHANGE GLOBAL $post, SO YOU SHOULD RESET IT'S VALUE TO BE COMPATIBLE WITH PLUGINS AND SO ON
    wp_reset_postdata();
?>

Ordered lists (OLs) would be much better than paragraphs (P) in this case (since these are LISTS of animals ORDERED BY name).