My first idea was a "merge sort" (well, at least the "merge" part of it). Luckilly you say that the files are already sorted so this is easy. But I still don't think it is as easy as extending what gaspodethewonderdog came up with (since you said in the chatterbox that you wanted both additions and deletions).

sub compare {
    my( $old, $new )= @_;
    open OLD, "< $old"  or  die "Can't read $old: $!\n";
    open NEW, "< $new"  or  die "Can't read $new: $!\n";
    my %old;
    while(  <OLD>  ) {
        chomp;
        $old{$_}++;
    }
    close OLD;
    my @new;
    while(  <NEW>  ) {
        chomp;
        push @new, $_   if  delete $old{$_};
    }
    close NEW;
    my @old= sort keys %old;
    print "New sites:\n\t", join("\n\t",@new), $/;
    print "Old sites:\n\t", join("\n\t",@old), $/;
}
[download]

Then use Alabanach's idea for deciding which order to compare the files in.