I forgot to cover racial variants. I love the environmental races from Unearthed Arcana. I think themes would be good here and not just for non-humans.
One of the best things 4e did was remove most of the non-biological aspects of race- Personally, I think they should have gone all the way (Things like Group Diplomacy and Half elf Dilettante should be feats in my opinion).
What I would like to see character generation include
a) environmental themes: Arctic, Cavern, City, Desert, Forest, Jungle, Marsh/Swamp, Mountain, Plains, etc.
b) culture: hunter/gatherer, Foot Nomads, Horse Nomads, River Nomad, Dwarves, Elves, Noble, Urban, Urban (street), Special: Apprentice (raised secluded by a wizard), Special: Temple (raised by a temple of a specific deity), Special: Monastic (raised by monks), etc.
These could even be made more specific based on the campaign. Specific clan, tribe, or Nation (e.g, Stinky Marsh dwelling Dwarves, Dragonspine Mountain Dwarves, Ghostwalker jungle halflings (halfing hunter gathers from a remote jungle), Mysterious Pointed Hat Man's apprentice etc.) Some like Big Townsman might give an occupational theme (craftsman, profession, performer) as its benefit.