Blue---->Lance: 15 levels (60-75)
Lance---->Red: 13 levels (75-88; 9 levels (75-84) if you exclude Pikachu)
Game Freak's idea of making these battles a "challenge" is to hope that impatient players will try to face them with their Pokemon sorely underleveled. It didn't work on their part because I took the time to grind. I've never been one to bring a knife to a gun battle, so to speak. Match Red with Pokemon within 4-5 levels and type match him, and he's cake. I OHKO'd or 2HKO'd his entire team with mine at level 84.
What's really stupid though, is how tedious it is to get through Mt. Silver (Rock Climb... WHY?!?!?!) to get to Red. I've only battled him once just because it's not worth my time going through that blasted mountain just to battle a kid with a defective voice box and his ugly little rodent.
To grind easier, I just abused the DS time settings and the Gym Leader rematches so it wasn't that tedious. All told, I still prefer the leveling system in Platinum.