Umbreon (unless you're waiting for a Glaceon). Try to evolve that Magikarp; Gyarados is great against the vast majority of enemies. Also look to evolve Staravia to Staraptor; Normal-typing might help a bit, and Staraptor hits like a truck. Also, you might want to use a password to find better Pokemon for Oichi; I forget if she's a mandatory unit in the main campaign, but her Jigglypuff is worthless this late in the game.
Tactics-wise, typing is always the key concern. Staravia/Staraptor and Rufflet (but not Braviary) are interesting, as they're part Normal but have Flying attacks. Obviously, don't bring Gallade or other Psychics, even though it's fully evolved. On the field, be aware of the flames, since a status hax may be enough to screw you over; learn their range, and avoid them. Keep your Pokemon grouped together when you advance; the shifting statues may impede your progress, but don't rush ahead, as that'll allow No to gang up on the vanguard.
If it still goes poorly, spend a few months grinding. The main game is very forgiving; this is where you learn the flow of the game and what battle strategies you prefer. There's no rush to win, since the computer will never invade you and doesn't grow stronger.