#1 The book itself
A very complex math or logic book can be a real trial for someone new to the material. If there is any growth in our hobby, it's been how our game texts have improved year after year in terms of their technical writing aspects. How clear are the game rules to the reader? How concisely are they written? How accurate are the illustrations? Keep It Simple (Silly) really pays off here. I understand D&D can be a big game with long books of rules. Making those games as easy to read as easy to comprehend as possible is an accomplishment for good authors.
Part and parcel to this is the DM's Screen. Quick and easy reference to tables, roll types, maps, and other lists is central to easy DMing. I believe that what even goes on this screen is an act of individual expression by each DM.
#2 The Character Sheet/Record Log
This is all about the interface. Imagine if your game had not a dozen or two dozen scores, but a thousand times as many. Would you even play it? Even on a computer? Early on the game only had about two dozen scores to keep track of. With skill lists, feats, powers, conditions, and so on the number has increased considerably. With the reference to some Classes having a rarity type relating to how complex they are to play I think they mean base class interface. Thieves have a good number of abilities, Paladins have numerous benefits and strictures, and Wizards may start small, but get very large at high levels. Fighters though start relatively easy and can stay that way.
I think part of this complexity will be about the amount of modularity added by each player, but the base class choices could decide some of it. I applaud that we won't have standardized uniformity across all classes with the same statistics. How simple each will be at the base core game level remains to be seen.
#3 The Adventure Modules
I like to explain that my game is kind of a blueprint for a Rubik's Cube behind a screen. Level 1 is a 2x2 square per face puzzle. Level 2 increases this complexity to 3x3 per face. This continues on so forth with rising complexity, but with each level building upon an understanding of the previous level. Of course this is an analogy as its more of a simulated world environment and much of its design divides out by class with a nod to ability scores, race, and so on, but this generally gets the gist of the idea across. In my game high level means highly complex adventure environments. Being prepared for those often means powerful and sometimes numerous abilities to engage with them capably. However, my game is built upon the understanding that PCs will have advanced from low level up unto their current abilities and corresponding challenge level.
Somehow I doubt this will be in the game, but it's possible they will assign general difficulty to adventure modules in the future. Part of it depends upon the PCs involved of course. And the group of players themselves typically choose these too.
#4 Combat complexity and Other simulation module complexity
With a modular game the core is going to be relatively simple compared to the same with lots of add-ons. I'm guessing the modules, like a tactical skirmish combat system, will have varying complexity and be optional. Almost all of the advanced D&D versions have had some degree of highly complex combat, if under different designs. Having this depth of game play can be a real benefit for those who want it. Making it optional means those who prefer other methods can use their own preference. To me, this complexity is all about options and even entirely modular games in their own right that can be used to depict particular fictional set pieces. Not only do I expect to see a lot of these, but I expect the complexity levels will vary across the board for many of the same play spaces.
With OD&D I still use Outdoor Survival and Wooden Ships & Iron Men. If you never go and head off path outdoors, you'll never see the first. If you never direct a waterborne vessel, you'll never see the second. I have no concern either way and I like that other games may have other modules and we as players could go hunt them down, if we so desired.
#5 Emotional complexity
This often doesn't come up with rules, but with the personal investment by players. Difficult situations can lead to difficult choices. Allowing one's self to be caught up in the in-game situation can lead to personal emotional challenges, but can also result in personal emotional fulfillment. All of which is to say, this game can push you, you can allow yourself to feel the pressure, but it can also be a great release for fun.
I see backgrounds, setting suggestions, personal stories and goals as marking what is emotionally relevant to the players. This element is really less about the game rules than about the DM placing content within the game for players to engage with. I'm hoping D&Dn will address creating, personalizing, and establishing characters in the game as well as the necessary table rules to ensure every player feels comfortable during play. Even if this is simply explicitly stating a "Time out" or role playing safety words, we would be improving on the past. Let me tell you, I've played the Dictionary Game (aka Balderdash) with my teenage nephew and we need table rules for that game too - at least when he plays.