As if I have time to take a vacation! 
But assuming I did, how are the accommodations? I need: a bed, a shower, a Western-style toilet. I’m not one for five-star establishments. From what I’ve seen, food seems to be cheap. How much is airfare? How much are hotels? When is the best time of year to go? (I’m not a fan of hot, humid weather; but whaddaya gonna do?) Ho Chi Minh City, or Hanoi? Or both?
Don’t know about air fares, but Ho Chi Minh city had some of the best super cheap hotel rooms I’ve ever experienced. They were $5 in 2001 for a clean room with fresh sheets and its own en suite bathroom with western toilet. Obviously this is going to be a lot more expensive now. The room and bathroom was nicely tiled. This was in a small 10 room family owned hotel. Outside of Saigon, my accommodations got crappier, but no more expensive.
Seriously, Vietnam has some of the best low budget travel infrastructure of anyplace. Of course, the food is cheap and to die for.
I’m happy up here in the Pacific NorthWet, but there are some things I miss about SoCal. Good Vietnamese food is one of them. I used to work not far from Little Saigon, and I have yet to find the variety and quality (and price!) up here. We may be going to see a movie tonight, and it happens that there’s a Vietnamese restaurant very close to it. Roomie has only had some phở and gỏi cuốn that I brought home from Seattle one day, and I think she needs more exposure to the cuisine.
I spent a few days in Saigon in, um, 1999? 1998? I can’t believe it’s been that long. Everything was cheap. Really, really cheap. Like, I kept wanting to give people more than the asking price. Also, as has been said, the food was really, really excellent. The road trip to the Cu Chi tunnels was fascinating.
On the downside, my necklace was snatched outside of the Ben Thanh market.
If I were to ever go back to Vietnam, I would put Halong Bay on the agenda. I’d also like to see Hanoi.
Just saw this thread while searching for something else. We went from North to South in Vietnam last year. There are some very good places. Liked Hanoi much better than Ho Chi Minh City. Much more character, especially in the Old Town, and it just turned 1000 years old last year. I can’t really recommend the place we stayed, which was in the Old Town; we went with someone else’s recommendation instead of our first choice, and while it was okay overall, we’d stay somewhere else next time. But we did spend two nights/three days on Halong Bay, arranged by Ocean Tours in the Old Town, and we can highly recommend this outfit. Beware of people or agencies offering cheapie deals for Halong Bay, as they could be downright dangerous (a boat broke apart and sank earlier this year, killing almost a dozen people, most of them tourists). Ocean Tours owns their own boat, which is very solid; the second night we spent at a guesthouse they own on an island.
Central Vietnam: We stayed at the Orchid Hotel in Hue, and I hesitate to say this, because it sounds like an exaggeration, but this is possibly the best hotel we’ve ever stayed at anywhere in the world. Definitely up there if not the best. They really went the extra mile. In-room safes. Loads of pillows on the bed. In-room computer with free Internet. They kept bringing fruit up to our room at no charge. The usual cable TV. Great location. Super clean (I think it’s pretty new). Kept arming us with water when we went out. Super-friendly staff. Good breakfast buffet. All for US$35 a night! Which they actually discounted when we checked out, because the city was doing rolling power blackouts, and the hotel’s neighborhood got hit with them twice while we were there, for maybe 12 hours each time; the hotel said even though it was not their fault, they felt bad about the guests being inconvenienced, so knocked some off everyone’s rate. I cannot recommend this hotel strongly enough.
Also in central Vietnam, do not miss Hoi An. A wonderful Old Town that miraculously was left unscathed by the Vietnam War. A World Heritage site. We stayed at the An Huy Hotel and can recommend it (even though after the Orchid Hotel in Hue, any hotel is going to pale in comparison).
In Ho Chi Minh City, we stayed at the Indochine Hotel in the Dong Khoi area of the city – good value and not a bad location. It’s only 1-1/2 blocks from the historic Brodard Cafe, immortalized by Graham Greene in The Quiet American. Alas! It has turned into a Gloria Jean’s Coffee shop. Really. But they left the Broward name up for Greene fans. I would stay at the Indochine again if I went back.
We had Western toilets in all our places. 
April was still nice and cool up in Hanoi but sweltering in HCM City. HCM seemed like any other hot and humid big tropical Asian city, and I would not be quick to return. Good to see once. Reunification Palace was especially interesting. That’s the old Presidential Palace, the front gates of which the first communist tanks burst through on April 30, 1975. I’m sure you’ve seen the footage. You can go all though the place now, it’s a museum. Hanoi I’d love to go back to, as it would be a good base from which to explore the Sapa region to the north, which we did not get to see.
I’d avoid this time of year, as it’s the rainy season, and the country is prone to tropical storms and hurricanes. Coolest will be about November-January or February, but you could actually see a lite snow up near the Chinese border even in April!
Hope this helps!