Rustboro City is where the first gym of Hoenn awaits. It is also home to the Devon Corporation, which Team Magma/Aqua are targeting.
Explore the City
As soon as you enter the city, your neighbor comes out of the Poké Mart and talks for a bit, then leaves.
Go into the Poké Mart and talk to the guy standing in front of the counter. He gives you TM54 False Swipe. False Swipe is a very helpful move that damages the opponent but won't make it faint, because the move always leaves it with at least 1HP, making it much easier to catch. Shroomish and Seedot can learn False Swipe, and you will encounter other pokémon later who can also learn it.
Go into the Pokémon Trainers School and talk to the teacher in the back of the room to get a Quick Claw. You can check the blackboard for more information.
Go into the house to the left of the Pokémon Center and talk to the guy there. He will give you HM01 Cut. After you get the Stone Badge from the Rustboro City Gym, you can use Cut outside of battle. Once you have the Stone Badge, teach Cut to a pokémon and you will be able to cut down the trees that block your path.
Go into the big building north of Cutter's house and go upstairs. Talk to the Ace Trainer to get a Float Stone. If a pokémon holds it, its weight is reduced by half. This can make certain moves do less damage to that pokémon. The next time you see this Ace Trainer, he has transformed into a Hiker because the Float Stone made him lose weight before he gave it to you...
In the same building, talk to the kid on the second floor to get a Premier Ball.
Go into the house next to the Rustboro Gym and talk to the boy. He wants to give you his Makuhita (named Makit) in exchange for a Slakoth. You can choose a pokémon from your PC Box or your party. You can catch Slakoth in Petalburg Woods, so go there if you don't have a Slakoth or you want to keep one that you already caught. Makuhita will be helpful in the next gym because Fighting-type moves are super effective against Rock-type pokémon.
You can go into the Devon Corporation building in the northwest part of town if you want to, but you won't be allowed to go upstairs.
From here, you can challenge the Rustboro Gym, or you can go northeast to Route 116, or you can go north to Route 115, although the only thing that you can do in Route 115 right now is get a Zinc on the beach.