I'd say leveling them together will be faster then leveling one first and the other second.
But leveling a single toon only, without the other, will be the fastest.

Kill quests, or collections where everyone gets the item per kill, will be faster with both toons in the party.
Both because you have additional firepower to kill things quicker, and because in BC and later expansions -- more toons in an area increase the respawn rate of creatures killed.
Also, you gain a very slight amount of additional experience, as the group bonus.

Collections or ground spawn quests, will take about twice as long for two toons as one.
So you're not any faster or slower running two concurrently, then you would doing one now and another later.
However, collections can feel very painful when you collect for multiple toons at one time.