I completely agree. Unfortunately, there are quite a number of examples of this across the country where the railway is either a terrible option or just not really an option at all.... After much consideration I couldn't think of any other places as large or as close as Leicester and Coventry.
I agree with most in your list. The Midlands is particularly badly served as a result of legacy networks and no real focus on opening up new passenger opportunities (part of which is made worse by a few line closures). There's been a huge amount of growth in some towns too, yet what has the railway done? Bugger all.
Anyway, here's a list of my top ones in the area (population figures from Wikipedia for the towns, not the boroughs, where possible; distances are a straight line from Google)
Northampton (225,000) to Leicester (329,000) - 29 miles
Northampton to Bedford (80,000) - 20 miles; and Luton (216,000) - 32 miles
Northampton to Oxford (150,000) - 32 miles
I'm not obsessed with Northampton or anything, it just happens to be in the middle of a poor area of connectivity, that is at the same time a well-populated and growing area.
You could string a few of these together, to make Nottingham to Northampton / Milton Keynes / Oxford, or Coventry to Bedford / Luton, for instance. I know there are capacity issues, but I'm just saying that if you were thinking strategically and trying to connect obvious markets, this is what you would be doing.