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.