Alicia is a character who appears at first in Oldale Town, where she grudgingly challenges you to a battle, claiming to be testing your strength. At that time, she has a Lv. 5 Sneasel, which can easily be taken down by Paras or a high leveled Baltoy. Otherwise, catch a Poochyena or Zigzagoon on Route 103 to help take it down.
The next time you encounter her is in Rustboro City. She challenges you to a battle once more, and this time she has a Lv. 10 Sableye, a Lv. 15 Sneasel, and a Lv. 10 Shuppet. A Dark- or Bug- type Pokemon should take care of them.
Once you defeat her, she heads back to Vendanturf town. This is where you next meet her, after you push the demons back through the rift with Gleis. She is accompanied by Pestilence, and you confront them in a battle. Once you defeat them, Alicia expresses her regret, and then follows to help build a new base for the Four Horsemen.