Why is the first query affecting the second query, even after wp_reset_query() and wp_reset_postdata(), but not on the second page?

I see a number of issues, aside from the use of query_posts ( this should raise immediate alarm bells ). I strongly recommend you don’t use the alt syntax, and that you minimise the unnecessary opening and closing PHP tags as it obscures your code.

Here is a cleaned up version of your first query loop:

if(have_posts()) {
    while ($sticky_query->have_posts()) {
        $sticky_query->the_post();
        if(is_sticky()) {
            ?>
                <div class="slide"><a rel="bookmark" href="https://wordpress.stackexchange.com/questions/92424/<?php the_permalink(); ?>"><?php echo the_post_thumbnail('full'); ?><h2><?php the_title(); ?></h2></a></div>
            <?php
        }
    }
} else {
    ?>
    <p>Sorry, no posts matched your criteria.</p>
    <?php
}
wp_reset_postdata();

You can immediately see that your first check is if the main query has posts, not your sticky query, the main query.

You then immediatley follow this with a query_posts loop, here is a cleaned up version:

wp_reset_query();
query_posts('showposts=3&paged='.$paged);
?>
<?php
if(have_posts()) {
    while(have_posts()) {
        the_post();
        ?>
        <div class="clearfix"><li>
            <h4><a rel="bookmark" href="https://wordpress.stackexchange.com/questions/92424/<?php the_permalink(); ?>">
                <?php echo the_post_thumbnail('full'); ?>
                <span><?php the_title(); ?></span>
            </a></h4>
            <?php the_excerpt(); ?>
        </li></div>
        <?php
    }
} else {
    ?>
    <p>Sorry, no posts matched your criteria.</p>
    <?php
}
wp_reset_query();

Immediatley you call wp_reset_query, despite not having a query to clean up. This makes no sense.

Then you go on to do a query_posts call. As mentioned earlier, this is incredibly bad practice. Never use query_posts. Instead consider using WP_Query as you did earlier.

So to summarise:

• Unless you have a good IDE and a very strong grasp of your semantic structure, dont use alt syntax while: endwhile; hint: if you think you can, you probably can’t
• Unnecessary tags should be eliminated. It’s ugly, it obscures your code, and it’s extra time spent typing. Separate out your html and your PHP logic, and dont do logic and processing in the middle of a html structure when possible
• Never, under any circumstances, use query_posts. There is no valid usage that is not covered by WP_Query or the pre_get_posts filter
• NEVER use query_posts
• Cleaning up after queries is good, but over-cleaning is bad and can interfere with other code
• Consistent code indentation is important