I think I'd have to go with
Blur - Coffee and TV
With runners up:
Kanye - All Falls Down because of the cinematography and it was before he went all egomaniacal
and
Prodigy - Smack my Bitch up, because of how fucking pissed everyone got at it, and the sweet twist ending. That one's fairly explicit - NSFW.
and
Massive Attack - Angel, but thats at least partly due to it being such a bamf song.