If you have a balanced team that is Lv70-80, you should be able to handle the E4 quite easily. Here is what you are going to face:
Lorelei:
Dewgong (Lv64) - Thunderbolt/Cross Chop
Piloswine (Lv63) - Surf/Flamethrower/Cross Chop
Cloyster (Lv63) - Thunderbolt/Cross Chop
Jynx (Lv66) - Flamethrower/Crunch/Shadow Ball
Lapras (Lv66) - Thunderbolt/Cross Chop
She has 2 Full Restores and will use them as soon as one of her Pokes drops below 1/3 HP. Cloyster will use Rain Dance, so feel free to use Thunder (100% accurate with RD) instead of Thunderbolt. Jynx is female and will use Attract, be aware. Lapras is a tank, so if you have Toxic, it will help.
Bruno:
Steelix (Lv65) - Surf/Earthquake
Steelix (Lv66) - Surf/Earthquake
Hitmonchan (Lv65) - Psychic/Aerial Ace
Hitmonlee (Lv65) - Psychic/Aerial Ace
Machamp (Lv68) - Psychic/Aerial Ace
He also has 2 FR. DO NOT use Flying-type Pokes against the last three, as they are equipped with Rock Slide. Your best bet is to use Aerial Ace with a non-Flying-type or better yet, Gengar with Psychic. It can blow through the last three with ease since it is Immune to 75% of their moves. Be aware though that Hitmonlee has Foresight as wel.
Agatha:
Gengar (Lv66) - Crunch/Shadow Ball/Psychic
Misdreavus (Lv65) - Crunch/Shadow Ball
Crobat (Lv66) - Ice Beam/Thunderbolt/Psychic/Rock Throw
Arbok (Lv68) - Psychic/Earthquake
Gengar (Lv70) - Crunch/Shadow Ball/Psychic
2 FR. Misdreavus is male and will Attract on you. Crobat is VERY fast and can hit hard. Go with a fast Electric Poke or a Poke that can take a physical and hit back with TB/IB/RS. Arbok abuses Double Team. The second Gengar (Lv70) knows Thunderbolt and Psychic so plan accordingly. Tyranitar with TB owns Agatha.
Lance:
Gyarados (Lv68) - Thunderbolt/Rock Slide
Aerodactyl (Lv70) - Thunderbolt/Ice Beam/Rock Slide/Surf
Dragonite (Lv66) - Ice Beam/Dragon Claw
Dragonite (Lv72) - Ice Beam/Dragon Claw
Kingdra (Lv66) - Dragon Claw/Earthquake
2 FR. Don't allow Gyarados any time to set up because it will first Thunder Wave, and then Dragon Dance in order to try to sweep you with Earthquake or finish your Poke off with Hyper Beam. Then again, this is the AI so you don't have to worry too much. A quick Electric Poke can handle it easily with its 4x weakness to Thunderbolt. DO NOT use an Electric Poke against Aerodactyl. It has Earthquake and it is one of the fastest Pokes in the game. Use a Water Poke with IB or Surf instead. Both Dragonite go down hard to IB, just be aware that the Lv70 version holds a Persim Berry and knows TB. Kingdra also likes to DD, and is only weak to Dragon-types moves. That said, its Def isn't that great so you can use EQ against it pretty well.
Gary:
Heracross (Lv72) - Aerial Ace/Flamethrower/Psychic
Tyranitar (Lv72) - Cross Chop/Earthquake/Surf
Alakazam (Lv73) - Crunch/Shadow Ball
Bulbasaur starter:
Gyarados (Lv73) - Thunderbolt/Rock Slide
Exeggutor (Lv73) - Flamethrower/Crunch/Aerial Ace/Shadow Ball/Ice Beam
Charizard (Lv75) - Rock Slide/Thunderbolt/Surf
Charmander starter:
Exeggutor (Lv73) - Flamethrower/Crunch/Aerial Ace/Shadow Ball/Ice Beam
Arcanine (Lv73) - Surf/Earthquake/Rock Slide
Blastoise (Lv75) - Thunderbolt
Squirtle starter:
Arcanine (Lv73) - Surf/Earthquake/Rock Slide
Gyarados (Lv73) - Thunderbolt/Rock Slide
Venusaur (Lv75) - Flamethrower/Aerial Ace/Ice Beam/Psychic
FOUR Full Restores. Heracross will use Counter, so either use a weak move to drop its HP down 1/3 before using a power move, or make sure you can OHKO it. Alakazam now has Calm Mind and Shadow Ball so plan accordingly. Tyranitar is a real ***** if you are not prepared. Naturally you would think to bring in a Water Poke, but that would be a mistake since this Tar knows TB. Go with Cross Chop. This Gyara is the same as Lance's. Exeggutor shouldn't pose much of a threat. Arcanine has Overheat, which is a good one shot, and it has Extremespeed that can be bothersome. Charizard knows Earthquake, so don't go running out an Electric Poke against it. Venusaur knows EQ too, but for some reason will never use it. Just roast it. Blastoise is just beginning for a Thunder/Thunderbolt.
It is very lame that when you beat Gary for the SECOND time, he still acts like he was the champion, but he can dream I guess. Don't think it would have been too hard for the developers to change that sequence, but what are you going to do, eh?