The OED's primary definition for Frank is "[a] person belonging to the Germanic nation, or coalition of nations, that conquered Gaul in the 6th century, and from whom the country received the name of France." The first citation is from Beowulf, "In Francna fæðm" ("in the grasp of the Franks"). The second sense for Frank is "[a] name given by the nations bordering on the Levant to an individual of Western nationality." For example, Burton observed that the inhabitants of Harar barred Europeans from their city because they "read Decline and Fall in the first footsteps of the Frank". I suppose that Europeans came to be called Franks at time of the crusades, since the crusaders were more French than not, in the same way that Americans came to be called Yankees at at time when New Englanders seemed to the rest of the world to be the prototypical Americans.
The OED cross-references the extended sense of Frank to "Feringhee", which is defined as "[f]ormerly, the ordinary Indian term for a European; in 19th c. applied esp. to the Indian-born Portuguese, and contemptuously to other Europeans."
Presumably this is the lexicographic inspiration for the Star Trek species the Ferengi, though the person who imaged the Ferengi language here was certainly not patterning it on French, ancient or modern.
Tim Buckwalter wrote to me that in his experience, this frozen synecdoche ("Frank" for "European") is found in Egyptian but not in Levantine Arabic:
"I found that Levantines and Egyptians made use of "French/Frank" differently. Although both used "fransaawi" (or MSA "faransi") for "French", only the Egyptians used "farangi" to denote "European foreigner". (Levantines would have pronounced it "faranji" if they had used it, but I don't know what meaning they would have assigned to it. ...). But the Levantines had an interesting use of "Frank" in the term "franko-arab", which they used for designating bilingual Arabic-European language talk typical of university educated people ... "
[Update: Trevor writes:
I don't know much about Yankees, but the term ifrang (caron on the g) is already used pre-crusades in C8th Andalusian and Maghrebi Arabic to refer to heathens from the north (ie tripartite division: Andalusians, Jews, Franks). Now that we all belong to ancient nations desirous of independence, ifrang tends to get translated as 'Catalan' or 'Basque' or whatever, depending on the translator's paymaster and/or party membership. According to Miquel's Géographie humaine du monde musulman jusqu'au milieu du 11e siècle (1975) the word was originally used by the Arabs to distinguish western Christians from the Byzantines (which may explain why it doesn't show up in pre-modern Levantine Arabic). Kfr certainly made it over the land route to parts of India in the first Muslim rush, but I suspect that Feringhee arrived in the subcontinent on dhows from the Gulf. Various other words were used by mediaeval Arabs in this part of the world to describe unbelievers, including kafir (see Byron's Gavour), rum (macron on the u), 'ilg and nasrani (I hate diacritics).
So my guess about the crusades as the source of "Frank = European" is apparently wrong; and it seems that the OED is also wrong in assigning the origin of the (various Arabic transliterations of the) term to the Levant.]
[Update 2: Lameen Souag writes:
Interesting post on Ferengis and Franks... I could add that: "franko-arab" is a straightforward loan of the French coinage Franco-Arabe; and http://www.emich.edu/~linguist/issues/4/4-492.html gives an impressively long list of languages using farang, including most of Southeast Asia and Ethiopia. I had always assumed the word was initially spread by the medieval Arab geographers; compare the semi-mythical country Waq Waq (either Madagascar or Japan in the medieval geographies), which in parts of Algeria is still a popular site for fairy tales. Note that, while it may not be used in the Levant per se now, it was copiously used there in the time of the Crusades - see Amin Maalouf's The Crusades through Arab Eyes, where he quotes relevant Arab chroniclers of the period - so your hypothesis may ultimately be correct... In Algeria we don't have the term faranj, but do still call the French and any other Westerners "Rumi" - Roman, or really Byzantine - or "gawri" < Turk gavur < Arabic kafir - which from Turkish gave English the word "Giaour".
]