It doesn't help that Rapidash has Drought either lol
By that point, you should have the lucky egg right? One thing I did was level up my pokemon to the mid 60's by battling a bunch of pokemon in Routes 103 in the water and 118 in the grass. Tentacruel and Miltank respectively have plenty of exp.
In my experience with the fight, Steven's first 2 pokemon go down fast, and he gets to Skarmory. Skarmory has protect, so if you get lucky, you can get a free turn of the fire types attacking Skarmory. If you can set up something (say, you have a pokemon with Swords Dance), you have a better chance of winning.
I'm almost done with the game, I have to train for the elite four; my first attempt failed lol. Spolier Warning: Wallace's first pokemon is a level 88 Metagross. Swept my team with ease lol