Spanish native here. Andalusian accent never was known by being difficult to understand. Have other associations, but never that it's difficult to understand.
For English speakers: North and Castille (middle) Spanish it's like vanilla Spanish. It's understood almost everywhere modulo some jargon. Kinda like English from the BBC or the NBC/NPR/CNN.
Andalusian Spamish it's like Southern English: Fast speech, ommited consonants and merged words and some loanwords from Arabic used in everyday words but for us they are like ancient Spanish (Arabic origin alcancia vs hucha). Kinda like the borrowings from Spanish in the Southern US Engish). Lasso vs lace/ribbon, aficionado vs fan and so on.