man... Star Guitar and the music video is where my love started.
My first introduction was 'Let Forever Be' via a music cable channel where you would call a toll free number and make a purchase to watch a particular music video. Think it as a music video jukebox. Any who, I took notice of the odd music video but never really went down the rabbit hole to figure out who the Chemical Brothers were. My internet access was limited, and when I did use it I was in AOL chat rooms getting cat-fished by grown men.
I'm a night owl, so most of this was caught at the wee hours (probably during the summer time). I also recall coming across a live show around that time and it had to be on MTV or MTV2 which had the Chemical Brothers playing "Hey Boy, Hey Girl". It could have been Woodstock 99, but the backdrop of Redrocks seems super familiar, I've still yet to confirm this memory.
Fast forward two years later, Star Guitar plays on MTV2 late night. I become completely infatuated with song and video, and take note of the upcoming album release which I buy it before a spring vacation trip down I take down to Disney World (I just received my first CD-Walkman the following Christmas). I would have Star Guitar on repeat for most of the car trip down to Florida, until I finally gave the entire album a try. My ears never heard such unique and futuristic music. I became fucking hooked. I even heard "The State Where In" at the Virgin Megastore in downtown Disney on my trip, and looking back in retrospect it was a rather strange track to catch in-store, but the timing of hearing it and the current obsession with the 'Come With Us' album, solidified my love for this group.
Edit: I'm now thinking of odd correlation of catching non-promoted song ("The State We're In") by Chemical Brothers in Virgin Mega Store and their first US gig, which was in Orlando.
P.S. - I'm drinking...