Demon's Gate
Quickly cast Slow on Demon's Gate. This creature can attack quickly even when slowed, but at least it's attacks will be more managable. Also, cast Barrier and Haste on the entire party to help protect against the Demon's Gate's Rush attack and Avalanche attacks. This also allows the team to react quickly to the Gate's actions. Having the Heal Materia will help to counter its petrify attack; otherwise you'll need a few Softs.
Try to keep everybody alive and around 1,000 HP and you should come out with the upper hand. The Gate is IMMUNE to both Poison and Demi(Gravity) spells and RESISTANT to Earth. You recieve the Gigas Armlet after defeating Demon's Gate.