The Red Dragon and the Demon's Gate have always been rather challenging for me. My strategy is just to shift everyone to the back row. I fought with Cloud, Vincent and Yuffie and equipped Cloud with Long Range Materia and it usually paid off in the end. Vincent's Galian Beast pretty much does the killing for you. Climhazzard and newly acquired Bahamut just make the inevitable victory come just that little bit sooner.

I've never bothered getting Great Gospel. In fact, I'm overusing Aeris if she gets Seal Evil.