Starting on the boat after it's set sail is totally doable and a good inbetween. So we can totally go with that idea, if that's what the people want.

[@Yankee]
You might be waiting for a little bit then. :P

[@Double]
Well, players can't play as royalty anyway in this story, so at most, he'd be the son of a high-ranking noble family, like a Marquis, Margrave or Count.

As for a thief and proper nation to hail from, that depends entirely on if you're choosing that class because he's actually good at stealing and skulking, or because he's a noble's son and doesn't have much in the way of practical, actual fighting prowess (in which case, he could just as well be the 'NOble' class from Three Houses).

The nations that foremost make use of the thief "class" are Tinace and Brelya. The empire also makes use of them as spies/informants. They're not very prevalent in the other three countries though. But, again, any class can hail from any country if that's what you want. But if you're looking for actual, lore-relevant reason to be a certain class from a certain nation, then the above is what you''ve got to work with. ^^