Last year I wrote about about backloading complexity, specifically applied to skills. In response, Jeffro wrote an excellent post about extending that idea to magic-users; in Jeffro's Infocom-inspired system, magic-users begin with only one spell, read magic, and must discover all other spells by finding scrolls. This is also a way of backloading complexity (because the players of magic-users do not need to know what the various spells do before the game starts or choose between them), but it is something more as well. It is diegetic in the sense that it ties the game mechanics to in-game events and situations. It is meaning first.
I think this principle can be extended even further. What if learning new skills or feats required finding a teacher or some other quest? For example, if you want to learn the mounted combat feat, perhaps you need to complete 1d4 missions with the local cavalry, and maybe you must journey to the steppe barbarians to learn mounted archery. Under such a system, feats would become a form of treasure, or at least an adventure hook.
Why not use this approach for race as well? Elves could be available as PCs once Elf-Land has been discovered. This is the way that Evan plans on handling reptoids in his Uz setting. Other nonhumans could also be accessed in this manner. In a sense, this is similar to the idea of "unlocking" options in video games. To take this to the logical extreme, what if you could play any race if you could convince one of them to first be a retainer (riffing off the traditional idea of being able to promote retainers to full PCs)? Thus, want to play a dragon? You first have to find and make friends with one. It would provide a nice incentive for parley, too. And give the referee an opportunity to show through play how a given species behaves in the particular setting.
One could even imagine having almost nothing at the beginning, and discovering everything through play (even class). Some modes of zero level play approximate this ideal, but in reality most of these systems allow players to plan things out and just make them wait for it (which is why I think many people don't like zero level play). What I am laying out here is a stricter idea how zero level is usually played, as spells or other mechanical bits may be entirely unique to a given campaign (though the two ideas could be profitably mixed).
This structure privileges exploring game worlds over exploring mechanical options. Players might not even know what feats were available until they have experienced the game! I realize this kind of game is not for everyone (there seems to be a sizeable contingent of players that groove on character optimization, if forum post volume is anything to go on), but I think this is a mode I would enjoy both as player and as referee. Exactly where one draws the line between character creation options and diegetic options is a matter for individual groups and referees to decide upon together.