Name: Lorelei

Pokémon: Dewgong level 54, Cloyster level 53, Slowbro level 54, Jynx level 56, Lapras level 56.

Use a strong electric type for the water pokémon and a strong fire pokémon for the ice types. That's all I can recommend.

Name: Bruno

Pokémon: Onix level 53, Hitmonchan level 55, Hitmonlee level 55, Onix level 56, Machamp level 58.

You should be able to beat this guy easily with a ghost type pokémon. My friend beat him with his level 40 Haunter. Psychic attacks are very strong against these pokémon.

Name: Agatha

Pokémon: Gengar level 56, Golbat level 56, Haunter level 55, Arbok level 58, Gengar level 60.

Special attacks work well, like fire blast etc. If you have a psychic pokémon that's strong enough, it would be excellent.

Name: Lance

Pokémon: Gyarados level 58, Dragonair level 56, Dragonair level 56, Aerodactyl level 60, Dragonite level 62.

No, it's not a typo. Lance has 2 level 56 Dragonair. Any pokémon that's strong enough can beat dragon type, but 'strong enough' means REALLY strong. Other dragon types are your best bet. Alternately, you could use a strong grass type for Gyarados and the Dragonairs and an ice type for Aerodactyl and Dragonite.

Name: Gary

Pokémon: Pidgeot level 61, Alakazam level 59, Rhydon level 61.

If you chose:

Squirtle: Gyarados level 61, Arcanine level 63, and Venusaur level 65.

Bulbasaur: Exeggutor level 61, Gyarados level 63, and Charizard level 65.

Charmander: Arcanine level 61, Exeggutor level 63, and Blastoise level 65.

If you want the best possible choices against his pokémon, I suggest a rock or electric type for Pidgeot, a psychic type for Alakazam, and a grass or water type for Rhydon.