Learn English – What part of speech is “that” in each of the following sentences that mean the same

Each is a Quantifier. Quantifiers, like Articles, are a kind of Determiner.

The quantifiers each and all (but not some or every) can undergo Quantifier-Float,
  for example     Each/All of them kissed her   ==>   They each/all kissed her.
  but not     Every man/Some men kissed her   ==>   *The men every/some kissed her.

In other words, while quantifiers normally occur before the noun phrase they determine,
in some cases they can occur before the verb phrase, like an adverb or a negative.
This does not mean they are adverbs; it just means they're acting like adverbs.
Just like the fact that a gerund may be acting like a noun in some cases doesn't make it a noun.

English has three different uses of that:

1. Subordinating that: I believe that pigs can fly.
2. Demonstrative pronoun that: That is not a pig.
3. Adjectival that: That pig cannot fly.

Both your examples are examples of the subordinating that.

Whether you say "It annoyed the pig that the boys painted it" or "That the boys painted the pig annoyed it" does not change the nature of the that. You just swap the two clauses around, is all.

And the that still does join them alright. Just try dropping it to see that it does.