The Song:

Electro-funk weirdness, using Aphex Twin's semi-trademark inhuman wailing to provide the melody. There is a French voice sample near the end, "J'aime faire les croquettes au chien", which roughly translates as "I like to make croquettes for the dog".
I believe I can hear samples of both Björk's voice and the ICQ "uh-oh" incoming message sound elsewhere in the song, but that's very likely to be my imagination.

The video:

Directed by Chris Cunningham. A sunny Californian-looking seaside setting. Features an unusually long pre-song intro with much posturing a la rap video.
alcaron: I believe the French expression is 'leche-vitrine', the explanation being that one looks through windows at things for sale/other people's things.