It's a great album. I remember being utterly startled when I first heard it.
I was a post-graduate with a 99% guitar-band world view (anything from Zep to The Smiths to the then contemporary Stone Roses), when someone I knew played it. Incredible, iconoclastic stuff.
Less worthy of acclaim, but equally altering of ear and brain was the debut NWA album. Someone hi-jacked the stereo at a dour house party and played a pre-release tape of it. It certainly struck a dissonant note or two in the face of endless U2, Madchester tunes hogging the airwaves.
And somewhere between those two releases Paul's Boutique took up residence on my turntable and in my brain.