Historically, French was the court language of Europe and therefore the the language of diplomacy. (US Passports include English, Spanish, and French; I think they used to only have English and French.) Of course, that's not going to happen even though Brussels is primarily Francophone.
I didn't propose French because both France and Germany are often accused to have too much control and influence in the EU so I think there would be a significant push back if either of them tried to impose their language to the rest of the union.
Furthermore Spanish is probably easier than French for any kind of objective metric you could throw at them. In particular Castilian is easier to spell and has a simpler phonology. On top of that Spanish is one of the most widely spoken languages in the world. I think it would be a strong contender for "lingua franca", although that might be my romance language bias showing.
