<?php

$books = get_terms( 'book_titles', array( 'orderby' => 'name' ) );

$previous_letter = false;

foreach ( $books as $book ) {

    // If the first letter is not the same as the previous book,
    // then start a new section.
    $letter = substr( $book->slug, 0, 1 );
    if ( $previous_letter != $letter ) {
        $previous_letter = $letter;

        echo "Here's all of the letter " . strtoupper( $letter ) . ' books:<br />';
    }

    echo '<a href="' . esc_url( get_term_link( $book ) ) . '">' . esc_html( $book->name ) . '</a><br />';
}

?>