My travel gear is my best investment but I tend to get 2 dives a day, every day, when I travel. Downside is the money spent and extra suitcase. Upside is I get to dive the same rig every trip and know the service history.
I use a good standard size hardshell suitcase with just the gear in it. When it's in it's own suitcase it makes it mentally easier since you're not struggling to readjust clothing needs in your primary suitcase. On most airlines it qualifies as a free extra checked bag because they classify it as sports equipment. Regs and my prescription mask are in my carry-on though for safety and peace of mind.
MY order and personal choices would be...
-Mask & Snorkel
-Fins (Mares X-Streams are light, powerful and fit in a standard size suitcase)
-Regulators (Apeks Flight... CRAZY light)
-BCD (Aqualung Outlaw... small and light enough to fit in a carry-on. Also converts to cold water with larger wing)
*At this point a Save a Dive kit specific to your gear is a great idea... o-rings, straps, mouthpiece, weight pockets etc.
-Wetsuit (Bare Reactive 3mm is as warm as a standard 5mm, requires less lead and packs smaller). I also take my Bare 3mm Tropic boot in as I like the sturdier sole for both the concrete surfaces at the dive-shop and the ladders on the boat.
If you're only diving once or twice a week on a trip then this is all way too much... but if you're hooked and dive every day you can while traveling this is really a great investment.