How do we know you're not a dragon, beholder, etc.?
Someone mentioned minions. Would adding them to a Legendary monster in its lair raise the CR? Say you add four or eight one hit point servant monsters, for example.
A couple of things are going on there.
4e minions don't exist anymore. If I recall correctly, minions had to take damage directly aimed at them to go down. So a fireball would leave minions alone. That doesn't exist in 5e, but you could work something up.
Adding minions who are just low level creatures does not change the CR of the boss /solo creature. It adds to the encounter XP budget. If the low level creatures (minions) are significantly lower CR to the point that they do not contribute or are completely wiped out by a fireball or two, then they do not contribute to the encounter XP budget.
For the thread in general:
I think that most people expect an encounter with a legendary creature to be epic. However, as has been pointed out, a creature of a given CR is still just a creature of that CR. If a DM chooses a single creature with a CR at the 4 person party's level, they must expect that it is just a medium encounter and the creature is going to go down quickly. This is even more true if there are more than 4 in the party. For an encounter to be epic, it really needs to be a hard or deadly encounter so that it makes it past 3-5 rounds. That means that the boss / solo has reasonably specced minions (and is no longer solo) or is a CR several levels higher than the party. An 11th level party of four would find a CR 14 Adult Black Dragon to be a hard encounter that would befit the dragon's status as a solo/legendary creature.
I have additional challenges to work through. I am converting a 3.5 adventure path. I also have 6-7 players weekly. For solo / boss combats I either have to add more minions or up the monster difficulty. On nice thing is that now that the DMG is out, I have the information needed to bump the CR of a creature up through increased HP to accommodate the additional PCs. By increasing only the HP, the creature still plays the same, but it lasts more rounds. For instance, I can take that adult black dragon and increase it by 180 effective hp to make it the same hard encounter for 7 11th level PCs. This makes the dragon last longer, but it doesn't hit any harder. So there is less chance of doing 1 shot knockouts with the creature. The beauty of this is that if you find your estimate of how much hp to increase turns out to be too much, you can always make the next hit by a PC be the 1 that takes the creature down. In this case, it isn't really fudging because you already fudged/adjusted hp up to make it a worthwhile encounter.