Considering how many moves one can lean,
Prinplup learn 6 in 8, except rock climb and Fly
Empoleon is the best HM, learning 7 HMs except Fly
Considering the source and combo
Bibarel / Empoleon + Tropius will be the best.
Also, considering timeline as below:
> After 3rd Gym, Breed Empoleon at Solaceon City
> After 4th Gym, [Fly] available
> Before/After 5th Gym (Great Marsh), Catch Tropius
> Before 6th Gym, Move Deleter to delete HMs.
If one get a female Piplup and bad nature
Breed a better one and use the starter as HM slave will also make sense
The new Piplup will still catch up considering its just 3 gym.
And the starter Prinplup can level up and become Empoleon in breeding centre, which is quite simple as well.