Give the ten most populous states 3 senate seats each, and the ten least populous states 1 senate seat each. Reapportion as necessary after every census. You might have somewhat unbalanced senate classes (and/or have to hold extra special elections), but that's not the end of the world.
Still not a perfect system, but it's a major improvement imo.
Except you can't change each State having the same number of Senators unless all the States agree. That's never going to happen. About the only changes that realistically could happen would be to increase the size of the Senate to 3 Senators per State or decrease the term length to 4 years so that each State elects 1 Senator per general election.