Solution: Divide Florida into two states (North and South). Give Puerto Rico to South Florida. Puerto Rico has much more in common (culturally) with South Florida anyway.

North Florida is heavily republican, South Florida is heavily democrat.

Status Quo is maintained.