Anywhere from 45-55 depending on your confidence and your level of skill. Deathguise was easy, and besides you can save after beating him. Kuja wasn't that bad. If the characters you're using are well equipped he won't be tough, even at levels in the 30's. Necron is easy if you have the abilities to withstand the negative status of his Grand Cross.

I don't remember what level I beat them at. I was a lot higher than necessary, as I did all the side-quests I could before I gave him a go. I'd already beaten Ozma, so both Kuja and Necron were child's play.