Don't let Dead Money's listed level requirement put you off from playing it first when making new characters though. The requirement is clearly originally placed there because it was a one-time scenario which you cannot return to, and it was the first DLC pack. As such, the recommendation is there for first time players, to warn them that it was a hard DLC and would basically require significant experience in the game's mechanics to tackle successfully.
On new character runs, with more experience in knowing how the game works, I would say that most players should have no problems at all going from Honest Hearts -> Dead Money, before tackling Old World Blues, even at a sub-20 level. If you're going for tackling the DLC as soon as possible, without focusing much on the main game, Honest Hearts can give a significant number of levels in a very short period of time, especially for lower level characters. That should give most characters enough of a lift to handle the Avellone trilogy in the "correct" order.
Does it suck that the way the Avellone DLCs are written make them not very friendly for out of order play for players who demand attention to detail? Absolutely. But since each DLC can't reference any of the other DLCs directly, it's a problem that can't really be solved easily. At least they balanced the DLCs such that high level players can enjoy them just as well. The DLCs remain pretty challenging regardless of how high your level is, so the range is really more like 7-50 for Honest Hearts, 15-50 for OWB, and 20-50 for DM. They definitely scale up for higher level characters.