Actually, I started an FC with a mule character directly after finishing the tutorial quest in the Adventurer's guild and picking up the gil I'd sent myself via moogle mail. There doesn't seem to be any level or quest requirements. Just make sure you have the gil and can get the 3 sigs. The initial signatories don't even have to remain in the FC either if you just need them for numbers to start it. Great for private FC services for mules such as extra shared inventory space (the main reason I did it).