Well, if you're anywhere in the game, you'll have fought a trainer. They're different from wild pokemon battles in that you receive prize money, and that you can't run.

In G/S/C, they introduced the concept of rematches. R/B/Y trainers could be fought once, and that was it. In G/S/C, trainers would call you (the phone should be brought back) when they were willing to have a rematch. Now, in R/S, there's a device known as the Trainers' Eyes. This showed the type and name of a certain trainer, along with their "strategy" (nothing too helpful to you), type of pokemon, and quote.

Certain trainers could be rematched as many times as you want. For the first five times, the trainer's pokemons' levels will increase. After that, their levels won't go any higher.

There are a total of 69 trainers (there are NOT 70, and you do not get a trainer star for registering 70 trainers in your Trainers' Eyes). If you're missing one, then try Psychic Jacki on the Cycling Road. Enter from the north entrance and instead of going onto the road itself, go between the trees to the east. Also, Wally will be registered in your Trainers' Eyes after battling him on Victory Road. All other encounters won't show up.

Right, here are all 56 trainers, the 8 gym leaders and the Elite Four. Click each pair to see the location, pokemon and trainer's eyes data for each trainer.