While in “the loop”, detect if a post is the most recent

In addition to @Milo Answer (this avoids a senseless query, because we already got every needed information from the current wp_query):

if ( have_posts() ) : 
    while ( have_posts() ) : the_post();
        $headline_html_tag = $GLOBALS['wp_query']->current_post === (int) 0 && $GLOBALS['paged'] === (int) 1 ? '1' : '2';
        the_title( '<h'.$headline_html_tag.'><a href="'.get_permalink().'" title="'.the_title_attribute( array( 'before' => 'Permalink to: ', 'after' => '', 'echo' => false ) ).'">', '</a>'.'</h'.$headline_html_tag.'>', false );
    endwhile; 
endif;