Well their types go like this:
Will: Psychic
Koga: Poison
Bruno: Fighting
Karen: Dark
Lance: Dragon
Considering I have a Spinarak, Will was a major pain in the ***. It wouldn't have been quite as bad if it weren't for two Xatu though, which were the reason why I couldn't just spam Leech Life and hope for the best (although even that didn't work with the rest, admittedly). Koga and Bruno were easy due to Spinarak learning Psychic at level 53. Karen had a Houndoom that could outspeed my Spinarak and almost OHKO it with Flamethrower, and her Umbreon would constantly use Sand-Attack to make it that much harder for me to take it out. Lance had an Aerodactyl with Rock Slide, a Charizard with Flamethrower, and a Dragonite with Fire Blast; the first two also being able to outspeed me and had the ability to 2HKO. So yeah...those were my issues and such, and can tell you at least a bit about them I guess?
EDIT: @roacherman: It says that in all the games, and apart from G/S/C I think I've had at least one Pokemon sitting above those levels at least once before I got the right badge, and they've never disobeyed me. The only time they did is if it was from an in-game trade, such as when I made the trade in Gold for an Onyx once. And it quit obeying me at level 10. Also no, the Spinarak isn't shiny. In Gold and Silver Spinarak was purple for some reason, and its shiny versions were just a lighter shade of purple. They changed it by Crystal though iirc.