Was listening to this today. This song specifically (as well as a lot of their 70s output after the debut, which I think is very accessible and enjoyable on first listen). I was actually into prog very early on, earlier than I was into metal, but it took me forever to be able to enjoy 4:35-7:55. Granted "enjoy" isn't the right word, since I think it's meant to be jarring, but it took me a long time to get to the point where I was able to listen to the song all the way through. How that bit resolves and melds with earlier elements later in the song is quite brilliant, but it definitely took me a long time to concede that.
Another one I remember. The first time I checked out Enslaved was because they were supporting Opeth on a North American tour. I was like, "that probably means they're good". I remember going and checking them out on Youtube and playing this song and being like, "this is the worst thing I have ever heard". Huge fan now of course, one of the best modern bands IMO, but it definitely took a while to click.
Honorable mention. I'm not sure it took me a long time to "get" ELO, because my mom is a huge fan and I remember listening to them when I was very young. Getting to the stage where you are confident enough to admit to other metalheads that you "get" ELO. Now that's another matter entirely. They are known for pushing the envelope in a lot of ways by people who actually know their shit. But the amount of people who just write them off because of the cheesy pop parts and the helium harmonies are missing a lot of the advanced stuff that had never been done before arrangement wise. The fact that most people refuse to include ELO with other envelope pushing prog bands is stupid.
Besides, one of ELO's drummers went on to briefly drum for Black Sabbath. So get fucked if you don't think they have metal cred.
Bands I am still waiting to "get" but am open to the idea: Sadistik Exekution, Manilla Road
Bands I will never get: Tom Waits, anything involving Neil Young, Prince, KISS,etc.
And since I know someone is going to be like, "Prince was a genius", I will pre-emptively say, he very well might have been. But his songs still sucked. His lyrics are fucking creepy and/or stupid. He was a pretenious douche and a conceited Diva who was infatuated with his own reflection. And if I am in the mood to hear someone with a royal title sing in falsetto, I will listen to King Diamond. For someone who never speaks in anything other than an effeminate whisper and uses numbers in place of letters to talk 2 U that guy takes himself way too seriously. I don't get Tom Waits, but at least he's not an insufferable twat like Prince.