Personally, I suspect Orthodox Christianity would be the better pick.
Well, it could be better in the terms of the earlier creation of the unified Russian-Lithuanian state (there were numerous dynastic marriages so the ethnic identity of the rulers would not matter), which would just by the virtue of its size be one of the greatest regional powers (the GH being the second one).
However, I think it is wrong to dismiss Islam. The Golden Horde and the Ottoman Empire are strong in this period.
Though I think to get a Muslim Lithuania, you'd need Lithuania to hold out as a pagan power for another generation. Converting to Islam only really starts to make sense a bit later on from the OTL date Lithuania converted, when the Ottomans are crashing through the Balkans like a cannonball.
In Islamization scenario Lithuania does not have to wait until the Ottomans arrive into the region. The Golden Horde had been converted into Islam during the reign of Khan Uzbeg (Öz Beg) - 1313–1341. Territory the Golden Horde controlled at that time bordered Lithuania and after Öz Beg's army killed
Lev II and his brother
Andrey (co-kings of
Galicia-Volhynia, and last of the
Rurikid Dynasty) in 1323, the
Grand Duchy of Lithuania and the
Kingdom of Poland had access to control over Galicia-Volhynia. The Lithuanians defeated the
Rus' boyars and occupied
Kiev and its surrounding areas. In 1337, the joint Russian and Horde army penetrated to Lublin. In 1340 Uzbeg sent an army against Casimir III but it was defeated at Vistula.
So, if we assume that Uzbeg is ready to support Lithuanians vs. Poles in their fight for control of Galicia-Volhynia then Islamization of Lithuania (or rather of its pagan territories, most of the rest remain Orthodox) may make a political sense. Taking into an account that during this period there were no noticeable religious tensions between the Islamic Horde and its Orthodox Russian subjects, the schema could work: from the Orthodox point of view the Muslim rulers who did not interfere into the religious affairs of the Orthodox subjects had been much better than the Catholics who would and did try to push a conversion.
Alternatively, not Timur the Lame would probably make Islam an attractive choice for Lithuania, since the Ottomans were wrecked by Timur (set back by a generation or more) and if memory serves, the Golden Horde were also.
Memory serves you well but Timur, even during his raid on the Golden Horde was too far (geographically), too late and for too short period of time to provide any meaningful stimulus. If anything, destruction of the Golden Horde removed such a stimulus making it too weak.
Lithuania, as part of a triad of Islamic powers with the Golden Horde and the Ottomans would be interesting.
"Interesting" for its neighbors, most definitely. As in "let you live in the interesting times".
Among other things, it would mean that the old raiding and slave trading business will be kept alive at least for a near future.
I think this is the real problem with Lithuania aligning with the Knights, I just can't see the knights behaving themselves.
Which somewhat assumes that Lithuanians did "behave" themselves and were innocent victims of their neighbors' aggression.
AFAIK, this was not (given a slightest opportunity) the case: raiding the neighbors was their routine business. To quote from Adam Mickiewicz (hopefully, nobody is going to accuse him in being anti-Lithuanian
):
Doughty Budrys the old, Lithuanian bold,
He has summoned his lusty sons three.
"Your chargers stand idle, now saddle and bridle
And out with your broadswords," quoth he.
"For with trumpets' loud braying in Wilno they're saying
That our crmies set forth to three goals;
Gallant Olgierd takes Russia and Kiejstut takes Prussia
And Scirgiell - our neighbours the Poles,
I mean, the writing was already on the wall for the knight's racket when Lithuania converted, but they didn't change course until the Poles and Lithuanians crushed them.
The "knight's racket" was a rather complicated thing which could not be narrowed down to a single item like offending their neighbors. Order's history was not just a history of the raids or conquests but also a history of turning a wild area into the most economically advanced area of the region. They managed to create an economically viable state which, unfortunately for them, suffered from the internal conflicts between the Order itself and the "estates" (nobility and the towns) which were subordinate to the Order and which wanted more "liberties" for themselves (and as a result, looked for Poland as a place where they could get them).
EDIT: Jewish Lithuania is, of course, quite an interesting idea!
But completely unrealistic.