It really isn't so hard if you have the right moves equipped. You need a strong electric move such as Thunderbolt to take out Lorelei if your Pokemon aren't yet at high levels.
For Bruno, all you need is a Pokemon with Drill Peck, Psychic, or Fly to deal with the Hitmons and Machamp, and something with Surf, Earthquake, or Giga Drain to knock off the Onix.
The old bitty (I can't remember her name) has Ghost and Poison types, so if you have a normal-type Pokemon, you can do a "revolving door" sort of deal to beat the Gengars (just switch PKMN until it has no PP left; it will alternate between Toxic and a Ghost-type attack over and over if you do this).
Lance is a bit trickier, but since he sends out Gyrados first, a good hit with Thunderbolt should even the numbers out nicely. Ice Beam or Blizzard is a must when dealing with his Dragon types, however.
Gary.... well, that's up to you, mate. Any Pokemon can win at the E4 as long as you train it properly and equip it well. Make sure you get those leftovers that the Snorlaxes were sleeping on!! You have to use the Itemfinder on the ground precisely where they were lying.