As always, there's a lot of grey areas - firstly the definitions of cities (e.g. Nottingham looks small because it's got very tightly drawn boundaries, whereas some places look bigger because they are, e.g. "Bradford" generally includes a very wide area and a few other towns) - secondly the problem with the "Intercity network" (given that BR didn't apply much consistency to what qualified - e.g. to get from Leeds to Manchester by InterCity trains you'd have to go south to Tamworth or north to Edinburgh and change!)
There's also the question of how big intermediate places are (e.g. London to Edinburgh includes a stop at Newcastle, whereas London to Glasgow doesn't serve anywhere of comparable size - same with London to Liverpool which doesn't serve anywhere major) - it's nog just about the population of the places at each end
I'm pretty unbothered about whether places hundreds of miles apart have a direct link - e.g. Brighton to Liverpool or Glasgow to Bristol - they are so far apart that there won't be many passengers on a typical day - nice if they get a direct but I wouldn't base the timetable around trying to link all of these far flung conurbations
I declare a bias, but I'd say that Sheffield to Leeds and Sheffield to Manchester are both worthy of consideration.
Sheffield to Leeds is twenty nine miles between stations as the crow flies, but there's only one "fast" train per hour (taking around forty five minutes, compared to the hour or longer that Northern services take, which means they generally get overtaken, so passengers base their journeys around that one service - I used to be a daily commuter on it, I'm using it again tomorrow) - this would be bad enough if it were just a Sheffield to Leeds shuttle - however it's the Plymouth to Edinburgh train, and the only service from the West Midlands to West Yorkshire, so would be horribly busy even without the Sheffield to Leeds passengers. Plus there's the city of Wakefield in between, which is a railhead for a reasonable area. We were meant to get an extra two coach DMU on this corridor, under the Arriva franchise, but obviously any commitments/ ambitions have been abandoned under the new public sector Northern!
Sheffield to Manchester is thirty two miles as the crow flies but the two "fast" trains per hour take little under an hour (maybe fifty four minutes on average). Capacity has improved in the last few years, as the choice between "two coach EMT 158 or two coach TPE 170" is more like "four coach EMR 158 or six coach TPE 185", assuming that both services are actually running. However the market is ripe for rail - it's hard to attract motorists away from simple car journeys but easier to provide an alternative to the single carriageway A-roads that are frequently closed in the winter months (the Snake has been closed for a few weeks now), so a better rail service could take a big slice of the market (compared to routes where you are competing with a high quality motorway network)
(Leeds to Manchester is thirty five miles as the crow flies, but has seen it's "fast" service increased from three to four to five per hour, plus 802s/ Mk5s, electrification happening, upgrades, HS2... good luck to them, I'm glad that they are seeing improvements, but all investment seems focussed on that corridor)