Demon the Descent: Need help with Ciphers pretty badly
I'd wait until you get a feel for the characters, but you do need to have them figured before they start buying Embeds.
Onyx Path offers a sample character PDF, which includes a completed Cipher for each.
The quick and dirty method would be picking Embeds that seem fitting to the character, then coming up with powers that use themes from both their linked Embeds.
I personally find that "Final Truth" thing at the end kinda lame. I'd recommend using it to give the players some sort of secret about the Chronicle, or the God-Machine itself.