Walkthrough
Whether you decide to challenge the Cerulean City Gym when you first arrive to Cerulean City or choose to go meet Bill on Route 25, you will run into your Rival immediately when you step foot on Route 24 (just north of Cerulean City). He'll have evolved his Pidgey from your last battle with him on Route 22 (if you chose to do said battle), also having captured two additional Pokemon since then. He'll be much more difficult to defeat this time around, but he'll give you the Fame Checker after this battle.
Rival (Bulbasaur Chosen): Level 17 Pidgeotto, Level 16 Abra, Level 15 Rattata, Level 18 Charmander
Rival (Charmander Chosen): Level 17 Pidgeotto, Level 16 Abra, Level 15 Rattata, Level 18 Squirtle
Rival (Squirtle Chosen): Level 17 Pidgeotto, Level 16 Abra, Level 15 Rattata, Level 18 Bulbasaur