Code to randomize within a filter

I was presented a scenario from my boss and was wondering if somebody could help me out. My sample spreadsheet attached has only 1,500 records but the actual one has about 10,000 records and was wondering if there was a code to help me reduce my sample.

I was asked to find a way to find a way where I could randomly select 2 records for each client. The catch is that the 2 records have to be different states.

To further complicate things, I have to do this once a month and for each month, I need records on states that have yet to be selected until all 50 states are selected, and then the process starts over again.

I was wondering if there was a code that could me with at least some of this process but any ideas, suggestions, comments, anything would be greatly appreciated. I don't know where to start.

Thanks!
Scott