Did you exit the gateway ship into the arks lobby, or exit the shopping area from the east first floor elevator or the second floor middle elevator?
Cofy should stop you in the middle of the arks lobby with an unskippable talk dialogue saying something to you when you hit level 20 on the alt character. Then you will get the client order:

The above picture is with my alt character who just turned level 20. It's not possible to get the client order without her stopping you / talking to you first in the middle of the lobby. Since that sets the flag for the client order.
And just in case, here's a screenshot of my character select screen with my main at 98 hours play time selected:
