Ok, a fix for this:
1. Change registration.php (/wp-includes).
BEFORE
if ( empty($display_name) )
$display_name = $display_name;
$display_name = apply_filters('pre_user_display_name', $display_name);
AFTER
if ( empty($display_name) )
$display_name = $first_name.' '.$last_name;
$display_name = apply_filters('pre_user_display_name', $display_name);
This change will make the default write to the DB on a user creation be "Firstname Lastname" instead of their login ID. But this isn't enough...
2. By default, on the profile edit page, the first line of the drop-down menu (and the default therefore) is, again, user login id. So when a user changes something on that page, it will write it back to the display name.
To solve this, we edit user-edit.php (/wp-admin) and move the line:
$public_display['display_firstlast'] = $profileuser->first_name.' '.$profileuser->last_name;
to be the first line, right under:
$public_display = array();
BTW, not sure if this last chance is absolutely crucial, but at least this way it shows up correctly on the user edit page. :)
Hope this helps someone else.
Have fun guys! :)