Violet City
Visit the Pokemon Center first of all, and if you have a Bellsprout (you can catch one on the route you just traveled) you can trade Kyle for an Onix as low as L3. It's fine if you don't. Now, there are two places you can go. Either north to Sprout Tower, or straight to the gym. I suggest Sprout Tower first for some EXP.
Inside Sprout Tower, make your way to the top, taking the stairs and battling the sages along the way. They all have Bellsprout, and Hoothoot shows up in their rosters several times. All that appears is Rattata during the day, but at night, there is an abundance of Gastly.
At the very top of the tower, there are three sages, one of which can be avoided totally, but the precious EXP. and cash he holds may be something you want. Approach the master sage, and your rival, ???, comes away from him, and speaks to you. He doesn't battle, but the final sage does. The prize is HM05, FLASH.
Now, you can take the gym challenge. You have to get the first badge before you can continue to Union Cave; a trainer stops you just past a PRZCUREBERRY tree south of the gym. Falkner the gym leader, and custodian of the ZEPHYRBADGE, is guarded by an easily defeated trainer, but he himself may not be so easily beaten.
Falkner has a L7 Pidgey and a L9 Pidgeotto, which are pretty tough if your Pokemon aren't at least around L8. Falkner gives up the ZEPHYRBADGE and the TM for MUD SLAP, an accuracy decreasing ground attack.
Outside, to the northwest, you can get Arthur to give you the HARD STONE on Thursdays. You can't continue much further west, though, as a weird tree that wiggles blocks the path. This tree happens to be a Pokemon, and when you battle and defeat (or capture) it later in the game, a hiker beneath Arthur's spot to the east will give you ROCK SMASH (TM08 ? ), used to break rocks with cracks in them.
Anyway, once you have the ZEPHYRBADGE in your possession, travel south of the gym to the road to Union cave.