I think modifying RotW should be the first goal, to introduce differences outside of Europe.
I really like the ideas of :
- China split up, but chains of events to unify Siam (extending up to indian and south chinese borders, and across the isles)
- muslim faith not having expanded so much (westwards yes, but less to the south and east, to leave more space to hinduism - perhaps a spread of hinduism in east & south africa)
- an orthodox Persia revolting from the Timurids (due to orthodox provinces), but keep Mameluks muslim (and Ethiopia/Nubia hindu)
- improved techgroup for Siam, Nippon, and some hindu countries (tough not too much compared to their neighbours)
- someone talked about Carthago, and gave me an idea : Carthago was beaten by Rome, but before the Third Punic War they initiated a big colonization/exodus to the Atlantic, and they're presently an oceanic empire, extending across carraibbeans, Azores, and some other isles of the North Atlantic, but without any contact with Europe, nor with America. First choice would be to go west or east with their explorers.
- either Siam of Nippon could get explorers, and incentives to explore to the east, to discover America from the west (for Nippon) and to the southeast, to Australia/New-Zealand (for Siam)
- a striving Vinland, either still owned by Norway directly, or independent, maps known or unknown (in this case, some events might give the possibility that upon discovery they'll fall under Norway's rule again)