This is my current Granada game:
I was a little held back by a coalition of France, Castile, Tuscany (which holds almost all Italy), Pomerania and Portugal that made me free up Croatia (that was almost immediately vasalized by my ally, The Ottomans) and give back Corsica, Sicily and Malta.
Unfortunately I don't know if I can achieve the re-reconquista. I mean Castile is now weaken enough and Portugal has no big allies, so I don't worry about them, but I'm not sure I can take back the Spanish provinces from France:
My biggest hope is the current English-French war, but currently it seems to go towards a white peace, I think.
I tried around 15-20 starts and the best one (except for this) was when Genoa decided they want Gibraltar and attacked me right at the start which gave me an almost AE-free Corsica to start my game, but for the rest it's very tricky as Castile attacks me almost instantly after the truce is gone, so I don't really have time to build diplomatic relations, so going for Urbino brings a huge coalition against me (Austria almost sure and sometime even France), East Frisia brings Austria and sometimes Burgundy and Irish provinces are fine, but England doesn't want to ally me even with a +2 diplo adviser. The most feasible method it was going for Ragusa while improving the relations with Austria and Venice. That helps me get The Ottomans as ally. Still doesn't stop Castile from getting Gibraltar and Almeria in the first war, but I can get Bosnia and sometimes parts of Serbia and later Croatian provinces.