For the first gym battle, Cheren uses Patrat and Lillipup at levels 11 and 13 respectively.
As long as your starter is at 13 or higher, you should have little problem beating Lillipup. For other team candidates, you can get Riolu at the Ranch, around level 5, though it doesn't learn a dependable fighting move until level 15 (Counter is a bit meh, in case of any critical hits). Pidove or Lillipup will be other good candidates, and even though Pidove will have trouble with Kamitsure's gym later on, it will help you at Arti's gym. It can also learn Fly, so it can be your early HM slave, until you get a Ducklett and give it 4 HM moves.
Lillipup with Pick Up will evolve into Herdier/ Stoutland with Sand Rush, so it's a good Pokemon to keep for competitive battling, if you're considering that.