Keep in mind that people are likely to change states no matter what the new map looks like, so population shouldn't be of huge concern.
Some people will move regions, definitely, but arguably if you draw the regions with roughly equal populations, then roughly equal numbers will be moving to and from each new region so population should still be roughly equitable in the end.
And here's my first shot at a four-region map:
edit: I only now realized this is literally Scott's four region map except MD is flipped
doubleedit: and furthermore wow I am terrible at addition apparently, the Southeast region has 39 not 50, I think I accidentally counted VA with the south when I did the counting