I would like to "choose" the nature of Kyogre and the legendaries. When is the best time to save? Before the battle? Or is it unchangeable?
Save immediately before the battle. For legendaries, the nature, IVs, and shininess are chosen when you enter battle with that Pokemon for the first time. For traveling Pokemon, this means they are locked the first time and won't change for repeat encounters, but for one-off legendaries like Kyogre, this means you can simply save before the battle and reload over and over until you get one you like.