I think the time for Peterborough and Leicester is when the later HS lines are being planned.
Nottingham and Derby should be served by a station at Toton.
Sheffield and Rotherham (possibly Doncaster) by an interchange near Meadowhall.
Leeds and Wakefield by Cross Gates
York ultimately by its current station, until the line is extended to Newcastle (which I would do quickly with a station between Darlington and Middlesbrough).
The major advantage of stations between cities, like Toton is that they serve large numbers of people in each city. Yes those making the journey across Nottingham to reach Toton have it harder, but traditionally it is easier to get round a city centre than compete with the congestion within it.
Looking at services post HS2(3) then I suppose what we will see on the ECML is something like:
1 tph Edinburgh - Newcastle - Durham - Darlington - York (interchange for HS) - Doncaster - Newark - Peterborough - KGX
1 tph York - Doncaster - Retford - Grantham - Peterborough - Stevenage - KGX
1 tph Leeds - Wakefield - Doncaster - Peterborough - KGX
1 tph Leeds - Wakefield - Retford - Newark - Hitchin - KGX
1 pth Hull/Lincoln (then stations) Newark - Grantham - Peterborough - Stevenage - KGX
If that happens you get a couple more trains per hour at the smaller stations, Peterborough becomes a major interchange to east anglia, journey times do not increase significantly and there is a better service south of Peterborough. For me this would actually be quite good compensation for thos ECML cities that miss out in the first wave of HS2.
I imagine it would be a similar story on the WCML where trains go down the HS2 line from Manchester, Some use the airport* station and some use the Warrington* station to pick up Manchester passengers. Some would come out of Piccadilly (addmitedly using the line through East Didsbury). There would still be services from the classical stations along the classical route, just each would pick up stops in the trent valley, at Milton Keynes (I imagine almost all) and maybe Northampton and Watford Junction would see a lot more services.
Coventry is close to Birmingham International HS station and should be provided with a good shuttle service from Coventry to the station to allow simple interchange (bus if necessary, but I think a branch line could be built to facilitate interchange)