I disagree that they violated copyright. If they're using a screenshot or a short clip from a movie that is definitely fair use. On the other hand, what Giphy is doing is copying the entire meme.

What? That's absolutely not guaranteed to be fair use. AFAIK there's no precedent for such things. And even if random people making memes is fair use, Giphy would still be violating the copyright of the original media by hosting nearly unedited clips for commercial reasons. The vast, vast, vast majority of memes are not transformative.

What would be the infringement? I would say any animated GIF (or whatever) should be defined as fair use across the board, since it's impossible to use it for anything other than criticism or comment. It's not exactly like Beastie Boys vs. Chambers Bros, but it rhymes with it.

Isn’t there a gif of the entire first Shrek movie?

Perhaps, but that's clearly not covered by fair use. Posting the entire Shrek movie as a GIF is not creating a "new meme".

a heavily accelerated 49px by 49px gif seems okay