I am traveling to Vietnam. My initial plan was to start in Ho Chi Minh, but due to a long story you don't care about, we have opted to land in HCMC and then fly directly to Hanoi. Since we are now buying another ticket, do I need to get our visas in HCMC or Hanoi? We will only have carry on, so there's no need to go to baggage claim.
Ho Chi Minh city is going to be your international point-of-entry and you will have to clear immigration there. So that is where you need a valid visa. You can get it there if you like but make sure that there is enough time between since the wait can be long, otherwise you will have to apply for a visa at the embassy closest to where you live.
My experience is at least 30 minutes just waiting for the visa to be printed. You will have to line up and that will depend on how many people need one but expect a good 10-20 mins. Then you have actually go through immigration with your newly-printed visa, so it takes another variable while.
If you need a visa for Vietnam, get an eVisa if possible, or a regular visa at the nearest Consulate. The pre-arranged visa, which is really not a visa on arrival, still requires you to get an approval letter ahead of departure, and queue twice once you're at the airport. There's no reason to waste time if you don't have to.
HCMC will be your point of entry, and you'll go through Immigration there. This will be sped up if you have already a visa, either electronic or a sticker in your passport.