Personally I think a "Salon" type place would be nice, like many others I played FFXI for a long time and after a while I did want to change my characters Hair style if nothing else. Right now I like my Miqo just the way she is but who is to say somewhere down the line I wouldn't want to add a scar or change her hair?

So if they do add a Salon I think the basics should include
1.Hair
2.Eye color(contacts come on)
3.Facial traits(like scars and such)
4.Magically changed height

As far as gender goes or a whole new race I would think if they did include a new race they might just let you change your character all together course that has to include your name because who is going to sincerely want to change their Male Roegadyn to a female one with a name like say Joe Smashrocks just doesn't sound right lol but then again there are some weird names out there.