There were some important cultures developed in Andalusia in the prehistoric times, la cultura de los millares in Almería, 3000 BC :
http://usuarios.lycos.es/losmillares/ http://www.aldearural.com/alpujarra/historia/millares.htm Celtics didn't arrive there I think, they were iberians and then they mixed in the celtiberian. Very important was The Tartesos Culture, known all over the Mediterranean sea by the Greeks and Phenicians. Other mediterranean cultures as Greeks, Cartagho and Phenicians had more influence in Andalusia. And overall the Romans which I think are as important even as the moors. It's easy to find things about Tartesos in any History web.
About visigotic, I don't think they left a big influence, as they were only a politic and militar ellite and the citizens were still Romans and lived with the Romans laws even in the visigotic times.