My kids love YouTube, and I encountered two videos recently that were both good songs with highly imaginative, entertaining animation: Daft Punk’s “One More Time” and Air’s “Sexy Boy.”
Of course another classic is a-ha’s “Take On Me”. Another interesting one, definitely weird and NSFW, is Radiohead’s “Paranoid Android.”
What are your favorite animated music videos? Especially ones with both a good song and good animated story.
On your mark, a music video created by Hayao Miyazaki for Chage and Aska, a Japanese pop duo. It’s not a conventional music video but more like an animated short which tells a story without dialogue but it’s excellent.
I’ve always been rather fond of Pearl Jam’s Do the Evolution. Maybe for the wrong reasons. 
Alan Parsons Project’s pulp comic inspired Don’t Answer Me.
I like “Move Your Feet” by Junior Senior. It features low-resolution pixel art made with Deluxe Paint for the Commodore Amiga.
This is the one I immediately thought of. It’s not the greatest animation in the world, from a technical standpoint, but I love the style so much.
South African band Dear Reader:Great White Bear - especially the break at 2:45 and the ending
Poor Leno - Röyksopp
and of course, any Gorillaz vid, but the first will do (although I think Feel Good Inc. is my favourite)
Count me in for that one, and also for a-ha’s “Take On Me.” I also love Dire Strait’s “Money For Nothing” even after all these years.
Green Jello: Three Little Pigs
Claymation, but animation nonetheless.
Oh! And the Scissor Sisters’ Mary for an honorable mention…recognize the animator? 
On that same note, Interstella 5555, the full length movie Leiji Matsumoto made for Daft Punk’s album Discovery. The first couple tracks were released as standard music videos, but the second half or so was only released in the full version. Awesome album, awesome movie, awesome (if very, very long) music video.
Shiny Toy Guns “Ghost Town”
Just remembered two more (with the same, unusual sort of “animation” - not sure if this was included in what the OP wanted, but it does qualify as animation):
Oren Lavie : Her Morning Elegance (currently my favourite vid of all time!)
Another South African one: Goldfish - This is How It Goes. It predates the Oren Lavie but isn’t as good because it lacks a story, IMHO.
Almost any video by Gorillaz! Jamie Hewlett FTW!
Similar to this is a video some friends of mine made for one of my songs, hope it’s ok to post it…
The TV Show is a quirky one. Considering the number of views I thought it would be in the OP.
The Ghost of Stephen Foster by Squirrel Nut Zippers. It’s basically an homage to old black & white cartoons in general and the works of Fleischer in general.
Long, and not just one song, but worth every minute. Free to download even the 1080p version.
Party In The C.I.A. by Weird Al.