Is there absolutely ANY indication on where a Xaela might start, or what class?

[Atoli]

I personally think Ul'dah would be the place to be. It's the city most friendly to refugees.

*bursts out laughing*
Ul'dah's view of refugees is a mixture of absolute hate and "Great, we can abuse and exploit them as much as we want until they die because they have nowhere else to go!"
Eorzean refugees came mostly to Ul'dah because it is the richest city and they gullibly believed that richest meant "has the most to share with those who lost everything", but were greeted with "we are rich because we don't give anything, now hand over what you have left, too".

I doubt such detailed information is available to tribes randomly travelling the Azim Steppe on a different continent, but even if it were, the starting city should logically be the town in which they arrived at first when they entered Eorzea.
That's why it's important to figure out how your character came to Eorzea in the first place - if he came by ship, Limsa is the most likely. Lots of players seem to treat Limsa as just a bunch of pirates, but most people in Limsa are normal citizens; even the pirates are mostly under the Maelstrom's rule and specifically only attack Garlean ships. But yeah, if you look around Vylbrand, most people are either farmers, keep livestock, and/or are fishers or crafters. Not necessarily nautical or pirate-y in any way. Actually, herding is something we specifically only see on Vylbrand (the Limsa island) and nowhere else, if I remember right. I don't think I need to mention how herding is probably a big part of the Xaela lifestyle aside from all the infighting between the tribes

If the OP's character somehow sneaked through Ilsabard though, Gridania would make the most sense (and the possible starting classes there being archer, lancer and a nature-y mage fit surprisingly well as both weapons are mentioned in the Xaela lore post, and as the early Mongolians had nature-related shamans, conjurer is probably the closest in terms of magic the Xaela have as well). They don't like outsiders, yes, and especially Au Ra who look quite a bit like the voidsent the Gridanians had to deal with before would probably be treated with some suspicion, but lore-wise, that would actually fit quite well, as the catch with Gridania is that they DO EXACTLY THAT. They treat you like a suspicious, unwelcome outsider, so playing through that starting scenario would probably feel very natural.

For Ul'dah, the only way one could arrive is per airship (if we are talking about arriving from outside of Aldenard), as it is located right in the center between the other two and its port is not meant for oversea ships. That seems more fitting to Raen nobility and merchants than a single Xaela refugee, but then again, that entirely depends on how you want to play your Xaela in the first place.

[Hinoto-no-Ryuji]

-snip-

I feel like I should note that the sea is PROBABLY the only realistic way that a character could go from Othard to Aldenard; airships are a rare commodity in Eorzea simply because of a dormant Garlean presence, and getting an airship out of Othard - which has an active, dominant Garlean presence - would presumably be much more difficult. Scarcity lends to conspicuity, after all, and it'd be much easier (and safer!) to get out on a boat. As for going across Ilsabard (!!), I imagine that would be just as if not even more difficult, especially considering that would require traversing the land bridge guarded by Ala Mhigo.

I don't see the need to restrict oneself to Limsa, though, even if the sea is the most realistic (and Limsa makes the most sense overall). After all, the WoL arrives in Ul'Dah and Gridania by carriage, and not by air or foot or anything, so I think the idea would be that your character arrived by sea and then traveled inland to their town of choice. Yeah, you'd have to have a purpose for going to that place specifically, but the game itself states what makes Ul'Dah attractive to immigrants and refugees even before the Domans appear (economic capital, so even if those in power are exploitive at best and hostile at worst, there seems to be a real chance to make a new life there) and writing a reason to seek out Gridania would take a fair less bit of effort than the mental gymnastics involved in arriving there across the land bridge (I mean, one could certainly do that, but it would be more than a little bit at odds with how the game presents things). Xaela arrives, seeks employment in areas s/he is skilled in, gets directed there - done.