I know I want to have language be a part of the game but it's unclear to what extent. The problem is that I may know a little too much about what it takes to make a fake language (enough to see that it's really hard) but not enough to actually do it for real. And simple word substitution feels like cheating to me now.

(plus, players would rapidly learn to translate on the fly anyway.)
At any rate, language is one of those things that affects everything. Properly done, it affects the random character names, the random town names... heck, even the names of garments and tools are affected by language. I kind of had to decide to ignore language early on other than a few token gestures (like the two sets of month names). I have thought about it, though.
I forgot to mention that in my idea the letter substitution for the main languages would be randomized per-seed. However, it should be noted that while the Al Bhed alphabet may make a name look like "CEINE", the pronunciation is entirely different, because the alphabet really is entirely different, rather than the logic of the language.
The way I see it, the only real way to make language in the game flexible and completely accessible to players is through randomization like that. Off the top of my head, there are about 4 languages with almost identical grammar to English (Afrikaans, Norwegian, Swedish, and the lesser known cousin of english called Frisian). I know that because one of my friends in particular is a bit of a language buff... and he never stops talking about it. ;-;
But yeah, my point is if the language is limited somehow to a set vocabulary , then it's not terribly accessible, and that can be a little frustrating sometimes. I'm saying that because it's impossible to account for every word and altering grammatical structure is near impossible for a computer to do right, given how people mangle english as it is. The way I see it, either language is accessible as frisian constructs or it's not. While names may be a tad different, I don't see any other options that really make language part of the
interactive experience.
Just my two cents.