Player is present with a small login window, and in that window is a button for new character (if player enters incorrect name/password, would say try again or say create a new character)
For new character creation, client would present a nice interface to the player, letting them choose race,class, and stats from pulldown menus and spinbuttons.
Client would use a requestinfo to get the race and class information.
Instead of rolled up stats, players would have a set number of points to spend on there stats (settable in the config file)
Player selects their stats, race, class, starting location, name, etc, and hits 'done' or the like.
Client sends this info to server, and server validates it is then correct (client should never send wrong data, but someone using a hacked client shouldn't be able to generated bad characters)
As part of this, the different classes would need to become archetypes, so server can know what they are.
Down the road, an advanced creation method could be used where player doesn't choose a class, but rather what skills they want (and maybe get a small pile of gold). That should wait for any skill changes to be made.