Regenerate user_nicename column

The obvious method would be to write a custom WP-CLI script to run through the table, extract the first and last names, use sanitize_title to create a new nicename and update the record. You’d also need to copy the first and last names in wp_usermeta as you mention, at the same time.

I’m not sure I’m telling you anything you don’t already know here.