Now I'm wondering if airspace spreads out horizontally from the coast the same way that shipping rights do.

I'd assume so, but a quick skim-read didn't tell me either way.

If it does, then they'd pick between going through Spanish or Moroccan airspace, because the straights of Gibraltar are narrow enough you can see Africa from Gibraltar.

From what I've read, under the United Nations Convention on the Law of the Sea when you have things like that strait where it is the only reasonable route between two bodies of international water ships and planes that are traveling between those two bodies have the right to pass through unimpeded.

If you want to do something other than just a continuous and expeditious passage through the strait than you do need permission from the bordering countries and have to obey their rules. But if you are just going straight (no pun intended) through then it legally counts as being on the high seas all the way through.

They should build a dam across the strait.