For my purposes, the 3 tiers are as follows:
Adventurer Tier: 1-5
Heroic Tier: 6-15
Epic Tier: 16-20
Interesting. This is very close to Paizo's definitions of low-, medium-, and high-level. The difference is that they place the mid/high split at 12th/13th level.
Honestly, I don't have an issue with the tiers or the level ranges used in 4e. There is a problem with the Epic tier, but I don't think it's to do with the actual levels used.
The game itself would be packaged in two different ways.
Unfortunately, presenting the game in two different ways is almost certainly a losing strategy. You're competing with yourself, and it means that instead of having one product that does reasonably well, you now have two that are both individually failures - even if the overall sales are exactly the same, or even somewhat higher.
My inclination is to build the game around a single Core Rulebook, and then present the rules in two(-ish) ways - the preferred route is to enter the game via a boxed set including a whole bunch of stuff,
including the Core Rulebook, but also offering the Core Rulebook for sale separately for experienced gamers who don't want all the extra stuff.
However, if this is believed to lead to a boxed set that is just too expensive (since it must now be a Beginner set
and include the Core Rulebook), then the next best thing is to do essentially what WotC and Paizo have both been attempting - have a single low-cost Beginner set leading in to the 'real' core rules.
Broadly speaking, I think the problem with the Red Box (and previous starter sets) is that WotC have considered them only as an afterthought, and have tried to make them a really low-cost product. The problem is, to hit that low cost they've had to cut the product right back, compromising its utility.
I would go into what I think should be in the Starter Set in some detail, but the truth is that the Pathfinder set is now
really close to what I think should be done. What WotC should do at this stage is take a good look at the Pathfinder Beginner Box, convert the rules to 4e (including the same 1-5 level range), fill the box with comparable goodies, and publish. Just about the only thing that I think could improve it further would be a CD containing a 5-level version of the offline Character Builder, including only those options included in the set (oh, and of course a link to the D&D site, and ideally a nice bright "Subscribe Now!" button).
The problems with the Epic tier are most difficult to fix.
I think the biggest issue here is that WotC don't have (or haven't really expressed) a clear definition of that the tiers are. I think they could do a lot worse than to simply and explicitly say, "At Heroic tier the PCs are a cut above the norm, but strictly mortal - think the Black Company or the Three Musketeers. At Paragon tier, the PCs are superhuman, but only just - think Lancelot or Aragorn. And at the Epic tier, the PCs are legendary heroes who do six impossible things before breakfast - think Achillies or Superman." Doing this puts everyone on the same page, it gives their adventure writers some notion of what to aim for, and allows them to properly focus support.
Additionally, they should build the game so that it is not just possible, but easy to build characters at the start of each of the tiers. At present, building a high level character seems to mostly be a case of building them at 1st level and then levelling them up, which is rather slow and painful. Also, you acquire a lot of powers, each with their own quirks and complexities.
I'm inclined to think it would be better if 1st level characters started with just a few powers (as now), as they gained levels they gained more (as now), but once they reached the end of the first tier they maxed out on powers - after that point they either replaced existing powers with more, um, powerful ones, or they simply upgraded their existing powers.
Combining these two would mean that playing an Epic character wasn't much more complex than playing a Paragon one, and it would mean that people could more readily jump in to the Epic tier.
One other key thing is probably quite important: I'm inclined to think that the game
shouldn't become more and more detailed as you go (beyond a point, probably reached at the end of the first tier). Instead, things should probably become
less tightly defined as you move into the Epic tier. Instead of having dozens of individual and very specific powers, the PCs should each have a few broadly defined powers that they can then apply as they go. Indeed, there's an argument that Epic characters should perhaps transcend the notion of powers at all, and should instead be able to tap into their Power Sources directly, improvising a huge range of effects as needed. That alone would make the Epic tier feel very different to anything that had gone before.