Originally the US was (were?) a collection of sovereign states which voluntarily came together to form a federal government. When a government is formed by equal and independent entities, equal votes for each state might arguably make sense.
Most states, however, have primacy over their counties, which is to say states create the counties, rather than the other way around. Counties, for all the dogged loyalty and cultural cohesion they sometimes inspire, are simply convenient administrative divisions, much like cities, boroughs, towns or school districts rather than sovereign entities. Some states, especially in New England, either don't have counties or only use them for minor purposes, such as judicial divisions. Some states (AK, VA, MO) don't organize all of their land into counties or county equivalents, but rather include independent cities or simply unorganized wilderness, which receive services directly from the state. Other states allow minor civil divisions to sprawl across and thereby blur county lines, such as in Florida. Also, due to the vagaries of geography, uneven population distribution or outright gerrymandering some counties are hugely populated while others are virtually empty.
Bottom line: counties barely exist.
But, back to the challenge itself.
One way to achieve an equal number of seats for each county in the state senates, while fulfilling one man-one vote, would be to have one state senator per county each of whom wielded a number of votes equal to the population of the county they represent. So, in the Texas State Senate, for example, when the senator from Loving County voted on a bill he would have 67 votes to divide between yea and nay as he pleased, while the senator from Harris County (Houston) would wield 3.6 million votes to divide as he wished. This would guarantee that there was someone at the table for each county, while not allowing rotten borough empty counties to ride roughshod over the majority of the people. It would also allow Senators to cast a vote more nuanced than simple yea, nay or absent. (Yes, Loving County Texas really did have a population of only 67 people, according the 2000 census.)
POD-wise, I could picture this having developed as a compromise during the Progressive era to achieve one man-one vote while allowing rural bosses to retain their sinecures, or even in a set of ATL decisions by SCOTUS during the civil rights era.