If you're on the Phoenix Cave then you need at least eight party members found to fill up both slots. I've heard rumours that this game can be completed at very low levels (then again what FF can't be?), so really it's more about how you setup your party and how much prep in terms of learned spells/equipment/curative items etc. There's no set level that you should be at at any point of the game, though I like to use the rule of three - When in doubt, level up three times (FF8 et al. notwithstanding).