Maybe that's not enough of a change. Maybe we should think bigger.
Neil Freeman takes realignment to a higher level, and considers what the map of states would look like if they were realigned the way Districts of the House of Representatives are. Here's his view of the 50 states (click the image for his site):

In our present format, the population of states ranges from 493,782 to 33,871,648. In Neil Freeman's depiction, the population of states will range from 5.4 to 5.6 million. Major cities and their suburbs are in the same state. His map restores the historical structure of the electoral college and the political alignment of the United States' federal system.
In this image to the right, I've overlaid the existing state boundaries above our regional map in Neil Freeman's depiction.In the areas that I'm familiar with, these boundaries make contemporary sense. Breaking Upstate New York into Erie, New England, and Susquehanna makes great sense. I think the Ohio split into North Coast and Sohio makes sense. I like the way the State of Allegheny works. I think that the States of Allegheny and Erie would be better off in the new structure than they currently are, combined in the same entity as Philadelphia.
I think we'd have better national politics with a state map like this.
I am a map geek, and I most appreciate a map that depicts reality in a new way and helps you to interact/navigate more effectively.
I just came across the notion of "upside down maps", which demonstrates what maps might look like if we weren't fond of "northism", the assumption that north is at the top of the map. Northism is just an assumption, it doesn't have to be that way. 



