In my opinion the Scottish accent is the most difficult accent to understand.
"Introduced" the Scottish accent via Youtube to some Mexican co-workers who are fluent English speakers and they freaked out. Will never forget one saying "WTF is this? How can this possibly be real?". Guy generally thought it was some sort of fake prank way of speaking and couldn't grasp that people actually spoke like that.
It's odd because Dutch itself, being a Germanic language, has a lot of pronunciation commonality with the most conservative of all English accents, Scottish. You can hear it in this video, where a sentence composed of common Germanic words is spoken in every Germanic language:
If it weren't for Trainspotting, which I adore, I'd be utterly useless at understanding Scots accents. As it is, I can just barely manage.
Honestly, I'm regularly surprised by how nice and patient people from everywhere are, paying attention to my words even if my English is not, even today, as good as I would like it to be. Including French people. Including British people.