Well, a succesful Genoese colonization of the Canary Islands could be a start. The island of Lanzarote is name after his discoverer, the Genoese Lanzerotto Malocello after all. Have the Guanches not revolt against him, and the islands used as a base for the exploration of the African coast. The Republic of Genoa, who AFAIK was already entangled in Iberian commerce and politics, strengthens her ties with the Iberian kingdoms, takes an effective role in the Reconquista, and is awarded Gibraltar after the fall of Granada. Then... Butterflies, I guess, but at least it gives Genoa a "place under the Atlantic sun".
I'm not sure "Rewarded" is likely - I expect Genoa would have to get into Gibraltar quick, and refuse to leave under any circumstances. Gibraltars value would be very much recognised since well, its named after the leader of the Muslim invasion of Iberia. Genoa needs defacto control over it. Although I do like the idea of Gibaltar becoming effectively an Italian-Style Republic, it could become absurdly wealthy as the gateway to the Med, especially this early.