If we're measuring this by plotting counties' population density against partisanship, and seeing who has the strongest correlation... I'm pretty sure the winner will be Delaware.
Counties are not the ideal unit of analysis for several reasons, but they are easy to work with, so I don't fault anyone for experimenting with the data just to see what happens. If we were actually attempting a serious ranking of every state we'd want to a use much smaller unit of analysis - ideally one that varies less, proportionally, in population (or, at least, we'd need to weight for it). And obviously there's no getting around the modifiable areal unit problem.
We're also not just interested in the strength of the correlation. As long we're sticking with ElectionsGuy's original question, we're looking for a state where the correlation between population density and voting behavior is strong and the degree of geographic variation in voting behavior is high.
Well, of course.
Though Delaware isn't
just a winner because it's a small sample size outlier, the urban/rural split is genuinely quite wide there as well. The widest in the country? I dunno. But it deserves to be in the conversation.