I would suggest to use hydrogen-filled blimps.
These would be only fractionally (~7%) less efficient than vacuum while having no structural problems.
Low Mars atmosphere density calls for huge balloons, but they would probably be feasible.
Fact Mars atmosphere does not contain sizable quantities of oxygen means mitigate a lot possible problems with hydrogen being highly flammable.
Sand storms shouldn't be a big problem as they are usually confined below 800m.
Mars has a lower atmosphere density, which means there's less pressure drop with altitude, which, in turn, means higher altitudes can be achieved with less buoyancy reserve.
If this seems acceptable we can try to compute required sizes and engine power.