I remember back in `95 building websites that were basically just animated gifs, (no judging i was a kid). I used some under construction ones because I had seen it everywhere and I was constructing!
Heh. I'd say that comment made it to Hacker News last year, but I already linked it in the Mefi thread! And then I got server push animation working on my server, & yes, it's really as hideous as people say.
Keep in mind that the idea of a document that might be different every time you pull it up was still kinda new.
So maybe the "construction" part was a meme, but I think the idea that you needed to warn people that this homepage wasn't "finished" yet was universal.
Hard to say if it was the first or not. It may have been "Here's my list of interesting web pages (most of them were probably links to other peoples lists of interesting pages, very recursive.)" I don't think the word meme existed then either.