So I did a lot of runs of Japanese Black, since I was borrowing it from a friend while he replaced his stolen DS. 4 runs, to be exact. The 4th was a hilarious megastall team I sent over (which ended up with Leech Seed/SR/Curse/Gyro Ball Ferrothorn pretty much owning the entire game). But the first three goes were more fun.
Each time I picked a different starter (Samurott, then Serperior, then Emboar). Then I picked a "secondary" for them (Excadrill, Scrafty, Galvantula). Finally, someone to fill in the cracks, as it were (Darmanitan, Haxorus, Krookodile). Type synergy wasn't really a big deal, tbh, since in-game only Ghetsis matters at all, and even then only his Hydreigon.
But the real story here was the support crew.
Cut is stupid. The monkey learned it and was promptly boxed.
I caught a Cottonee ASAP and got it to the point where it knew Stun Spore/Leech Seed, and then later Flash. And then it was DONE. Know what's fun? Messing with anything that's 30 or 40 levels higher than you with priority Flash and then lasting forever. Level 17 Cottonee even KO'd Kyurem because I Seeded accidentally once.
Roggenrola is sorta member #2, but I usually replaced any initial Roggenrola with a Boldore later on, since I refused to actually battle with any of the support team. Sturdy was the real key here. Switching my level 20-something into an attack and surviving it means a chance to heal up someone who matters. Mud Slap added to the fun, and then Strength for some utility.
And finally Ducklett. Surf and Fly make him the most convenient member to lug around. He's got nothing on Pelipper, though. However, the Duck never actually saw combat outside of a sacrifice when Boldore wasn't available.
They weren't meant to be a complete HM set, mind you. Waterfall and Dive are pretty irrelevant anyway.
So what'd everyone else use for their "utility" Pokemon? Obviously HM Slaves, but beyond that too, if anyone besides me plays like that.
PS: In case you're wondering, doing all battles with only 3 Pokemon ever getting EXP + Lucky Egg being moved around constantly = horribly overleveled Pokemon. I wasn't playing for challenge, though, but to collect a mess of Reshiram/Tornadus/etc.