I went through the trouble to do this once, and learned that it wasn't worth it. Not that it was too hard - I did it, but it required constant maintenance.
First, when a user registers, you must alter the login form to remove the username field, and when the registration form is submitted, you must INSERT a username, which where it starts getting difficult. The way I did it, was to give it a temporary name and then change the name when the user ID is known.
Then you must override the output of your login modules, the output of the reset password form, the login view of the component, the user account default and edit views....
And when Joomla releases an update that changes any of these things - you get to rewrite the overrides.
Maybe instead, you might consider giving them a "generate username" option....make it fun, or base it on their name, or whatever.
It isn't worth it.