I would say the route from Gravesend to Faversham is the part that needs speeding up. The issue is that it is practically a metro, especially Rochester, east - as many services converge and almost all stop at all stations, and provide a very busy local service too between the towns.
If you did Gravesend-Chatham-Faversham for instance, firstly you'd have howls (Rochester, Gillingham, Sittingbourne, even Rainham - all in a 1.5-2.m range, ie rounding errors, they're about the same) - and secondly you would have things catching up.
Like many lines, the end parts have to run local. Except, at Faversham, this de-urbanizes again and in theory can stand up much faster services, esp via Canterbury East. The coast line is arguably more stopping territory.
But I agree, that urban crawl - really starting east of Dartford - would be great to speed up. But it's all really testament to sprawl and that the Medway line is a mini-metro stretch.