California Love is on that list.
I think I gotta put Shook Ones pt. 2 there too.
Fight the Power for obvious reasons, but also, because they flat out start the song by saying 1989! and it still doesn't sound dated.
Then I'll go with In Da Club.
And as a surprise pick, Hov's Empire State of Mind. Big single and Hov summed it up perfectly. Radio friendly/"soft" sound yet the lyrics are not if you pay attention.
When I started this I was sure Nothin But a G Thang, Straight Outta Compton or Regulate woulda been on it. And some deserve to be on it more than that Hov song. But I tried to be objective and include songs from different eras too