Brendan's first battle was when prof. Birch was attacked by a Zigzagoon he had to pick either Treecko, Torchic, or Mudkip . After the battle the professor will give you a pokedex and will let you choose to name your Pokémon.
Second battle (Optional)
In pre-release of Pokémon Omega Ruby and Alpha Sapphire, he was referred to as Orlando though this was not shown much. The only obvious remnant of this name is the demo where the player's name is such.