I can see reasons why a Legion companion wasn't included - NCR own most of the territory, and the Legion is trying to invade that. So travelling anywhere with a Legion companion would be difficult without starting combat. It works with Boone (he shoots Legion on sight), because most places are safe to travel when you're NCR. Even so, I'm sure it could have worked....somehow.
1. Ask Caesar about help.
2. He tells Dead Sea to help you out.
3. You go back to Nelson and tell him Caesar's order to help you out.
4. He changes wardrobe into something less obvious.
5. His personal quest is about his appeal to Caesar to become a frumentarii, yet he has been stuck doing skirmishes on outposts, so now Caesar has an opportunity to test him. In the end the choices of his personal quest will either make him a frumentarii, a centurion, a praetorian or he'll stay as a decanus in the ending sliders.
How this would work is that high ranking NCR NPC's will open fire on him if he gets within 20 meters of them.
So you can choose, shoot NCR up, or infiltrate them, and Dead Sea has been training for either.
Cakewalk.