You'll have to take down some models to some of the funkiest beats in Pokemon history, man. This Gym is seriously the greatest, haha. The first Beauty uses an Elekid L27 and a Flaaffy L27. Take her down, then continue down the walkway to face the next Beauty, this one using a Flaaffy L27 and a Blitzle L27. Next up is yet another Beauty, using a Blitzle L27 and an Elekid L27.
After you take out all three of the Beauties, you'll see Elesa appear and it'll show images of her on the big screen while spotlights shine down on her. It's pretty awesome, haha. Take this opportunity to heal up (run back to the Pokemon Center if you need to), then get ready to take on the fourth Gym Leader in the game, Elesa!
She starts off with her Emolga, which breaks the rules of Electric-type Pokemon by being part Flying-type, giving it a total immunity to their usual weakness. Rock-type attacks are the way to go against it, so use any you've got. Teaching your Pokemon Rock Tomb (you did get the TM for that in the Desert Resort, right?) is a good counter to Emolga's deviousness. Keep in mind that Emolga, as well as all of Elesa's Pokemon, is capable of using Volt Switch, which will hit for fairly heavy damage and then switch out for another Pokemon afterwards.
The Flaaffy can be a pain because it likes to paralyze you, both with Thunder Wave and with its Static ability, so Cheri Berries can be a good remedy for that, or just administer Parlyz Heals when you have a chance. Thankfully, it doesn't hit overly hard by nature, but it is packing Take Down, which may hit for more than you thought. Try to avoid making contact with it as to avoid getting paralyzed with Static.
Lastly, she sends out her Zebstrika, which packs Volt Switch like the rest of 'em, but also has Flame Charge, a Fire-type attack that raises its Speed by one level afterwards. It can be pretty tricky to take down.
The key to beating Elesa is using Rock Tomb against her Emolga and then using Dig against her Flaaffy and Zebstrika. Both of these TMs are available in the desert, so make sure you have them and try to teach them to whatever Pokemon you think would make best use of them.
One sure-fire way to take down Elesa with very, very little difficulty is to go catch a Sandshrew in the Relic Castle (they're easiest to find there) and then train it up against wild Audino on Route 16 until it evolves at level 22. This is easy to do with the Exp. Share. Then, teach it Dig and Rock Tomb from the TMs you get in the desert. Use Rock Tomb against her Emolga, and then Dig against her other two Electric-type Pokemon for an easy win. They'll have to resort to using extremely weak attacks against you, due to Sandslash's immunity to Electric-type attacks. You can take her entire team out easily with a level 22 Sandslash. Just make sure you stock up on some Fresh Water and Parlyz Heal in case you need to heal.
After you beat Elesa, she'll reward you with the Bolt Badge, which ensures that traded Pokemon up to level 50 obey you without issue, plus she'll even give you TM72 (Volt Switch), which is an Electric-type attack that causes the user to switch out after using damage. It can be handy on fragile, quick Pokemon to do some damage and then switch in to something more resilient.
As you leave, she'll even stop you and then walk down the walkway along with you, which is pretty neat.