I finished my completionist run of SP with this team. I've made some changes to it for people who aren't tolerant to grinding, but everything about it that made it effective is still there.
I'll update this later with anything relevant regarding the postgame.
Infernape @ Fist Plate / Charcoal / Flame Plate
Ability: Blaze
- Flamethrower
- Close Combat
- Mach Punch / Nasty Plot
- U-Turn / Nasty Plot
Relevant replaced moves: Taunt, Power-Up Punch, Flame Wheel, Slack Off
Infernape is hard to turn down due to its speed, very strong attacks, and how few options exist for Fire-types in Sinnoh. Apart from OHKOing almost all trainer Pokemon, the Chimchar line can can blow through Roark with Power-Up Punch and Gardenia with Flame Wheel, plus sweep Mars, Candice, Byron and Aaron.
You should buy Flamethrower for cheap at the Veilstone Dept. Store. Close Combat combines for a fantastic STAB combination. I kept Mach Punch because it was still OHKOing targets that were weak to it deep into the playthrough, and it's nice to save PP on the other moves. U-Turn is a nice way to break Sturdy and swap to a Pokemon that can take whatever attack Graveler is going to use. You can replace either move with Nasty Plot if you want Infernape to solo some fights with Flamethrower; Barry and Aaron come to mind.
I used Taunt a few times for catching Pokemon that use status moves. I also think Slack Off is worth considering. Acrobatics and Stone Edge are options, but there were zero times I wished I could use them instead of my STABs. Fist Plate is on Route 215, but I found a Charcoal in an underground hideaway and a Flame Plate from mining. The Fire boost is preferable because you'll use Flamethrower most.
Staraptor @ Silk Scarf / Shell Bell
Ability: Intimidate
- Take Down
- Brave Bird
- Close Combat
- U-Turn / Roost
Relevant replaced moves: Wing Attack, Quick Attack, Double Team
Staraptor is a bit worse since they took away Return, but it's still an extremely strong choice for a playthrough thanks to its early availability, high attack and speed, strong moves, and relevant ability.
Wing Attack at level 9 is great and will OHKO unresisted enemies until you get Take Down, which is a strong attack long-term. You'll eventually get Brave Bird as well, which OHKOs most targets. Close Combat is wonderful coverage for Rock- and Steel-types. U-Turn (get early at the Veilstone Dept. Store) is nice for the same reason it's nice on Infernape, but you can also use Roost to help with the recoil moves.
You can hang onto Quick Attack and Double Team until you get better moves. Silk Scarf is a hidden item in Veilstone City near the Galactic HQ. Shell Bell is worth a thought, since it helps with recoil and Staraptor does so much damage that you'll actually get something back from it. Staraptor is good for Maylene and Aaron, and I used it against Lucian too.
Roserade @ Miracle Seed
Ability: Poison Point
- Giga Drain
- Sludge Bomb
- Sleep Powder / Stun Spore
- Synthesis / Shadow Ball
Relevant replaced moves: Absorb, Mega Drain, Grass Knot, Magical Leaf, Poison Sting
I like the Roselia line because it's available early, spreads status for catching things, has high stats, and can heal itself. I usually catch one on Route 204, but in BD/SP they took Mega Drain off Budew and made Roselia available as soon as Eterna City (via the Grand Underground). So now I recommend waiting until you get the Explorer Kit; that way you're not stuck using Absorb and don't have to faff around evolving Budew.
Another important point: fill your party with Pickup Pachirisu at Valley Windworks and keep them there until you fill your team. This will get you tons of free items, including Shiny Stone, which is needed to evolve Roselia and not available otherwise until Iron Island. Roserade is busted early-game, do it!
Miracle Seed boosted attacks OHKO most of things, are great against Graveler/Onix, and stop you using potions. (Get Miracle Seed at Floaroma Meadow.) You'll use a mix of Grass attacks before settling on Giga Drain. I went out of my way to get a Roselia with Sleep Powder in the underground, but Stun Spore works too. Sludge Bomb is available late (Galactic HQ), but it's a strong attack. Synthesis makes you use even less potions, while Shadow Ball offers neutral coverage for Pokemon that resist your STABs.
Apart from dominating the early-game, Roserade is strong against Crasher Wake, Bertha and Cynthia's Gastrodon and Milotic.
Gyarados @ Mystic Water
Ability: Intimidate
- Waterfall
- Crunch
- Ice Fang
- Dragon Dance
Relevant replaced moves: none
Gyarados is so nasty in BD/SP. It now gets Waterfall at level 21 (new!) and Dragon Dance at level 36 (instead of 44); with those tools, Gyarados can solo almost anything that doesn't have an Electric attack. You can add Ice Fang via Heart Scale (mine them underground) and Crunch at level 24 to get a complete set very early on, too.
Intimidating something turn one and setting up Dragon Dance is something you'll get used to. You can do this against many opponents, e.g. Barry, Galactic commanders, Fantina, Byron and even Maylene if you're a touch overlevelled. Ice Fang means Grass won't wall you, and Crunch has good neutral coverage for other targets e.g. Confuse Ray Bronzor.
Thanks to Magikarp's widespread availability, you can be choosy about when you add Gyarados to your team. I recommend doing it after you get the Good Rod on Route 209, since then you catch a Magikarp at level 18-20 and get Gyarados's dominant best with none of the Magikarp grinding. You can get Mystic Water in Pastoria City with Surf.
Garchomp @ Soft Sand
Ability: Sand Veil
- Earthquake
- Dragon Claw
- Crunch
- Swords Dance
Relevant replaced moves: none
Garchomp is obviously very good. You can get a level 15 Gible from Wayward Cave after beating Byron, but I recommend waiting until after Candice, because you can get a level 40-something Gabite from the Grand Underground that way. Just make sure you get Earthquake from Wayward Cave, and you're set.
Earthquake and Dragon Claw are strong attacks with great coverage. Swords Dance (buy at Veilstone Dept. Store) helps with the Elite Four and Cynthia, whose Pokemon can survive Garchomp's raw attacks. Crunch is for Bronzor with Levitate, and for when you don't want to spend PP elsewhere.
Garchomp is good against everything, but especially Volkner, Flint and Cynthia. I recommend using SD twice against Spiritomb then spamming Earthquake until she brings you down. The rest of the team should be able to clean her up, especially if you play on switch mode.
Magnezone @ Magnet / Metal Coat
Ability: Sturdy
- Discharge / Thunderbolt
- Flash Cannon
- Light Screen / Tri Attack / Volt Switch
- Magnet Rise
Relevant replaced moves: none
Magnemite is available in the Grand Underground beneath Route 216 (i.e. after Byron). It's worth using for how good it is against Team Galactic (Golbat, Purugly, Skuntank etc. cannot touch you), Cyrus, Candice, Barry, Aaron, Lucian and Cynthia. It's also very convenient because it comes with both STAB attacks when you catch it, and you can evolve it straight away.
Discharge is strong, spreads paralysis often, and works great with Garchomp in double battles. Replace with Thunderbolt (Valley Windworks w/ Surf) for the Elite Four. Flash Cannon is a strong attack for Pokemon that resist Electric. Magnet Rise helps with Candice's Abomasnow, Aaron's Drapion, etc. which know Earthquake. Light Screen helps with Cynthia's Milotic, Roserade and Lucario. Tri Attack can be used to finish off Pokemon with Sturdy, or you can use Volt Switch (get at Amity Square) if you want.
You can get a Magnet at Iron Island (before Magnemite joins your team). Metal Coat is also good if you're lucky to get a Magnemite holding one.