Get rid of the grid
We had a very similar situation recently, where our team had an air battle against flying foes with high movement rates.
A grid won't work, because unless you use a barn floor for the map, creatures with high flying speed will be off that grid in no time. You could use larger feet per square to rein it in, but in my experience (and as you say yourself), this still will not help:
Once you get into calculations of height and distance, as described in Niko's answer, you'll be spending your whole session doing trigonometry. I know, because we did. No fun. And as long as you use a grid, it is really hard to get away from that. We tried to spitball it all and loosely track movements on a large-scale 2-D grid, but as soon as it did matter if you can reach or shoot someone, out came the calculators to demonstrate to the DM that the distance was different than what he thought. And from what you say "the system should be prepared for the fact my players will likely make it 3d", your players are no different. So any kind of grid will not work.
The Air Combat Mini-Game
If this is a one-time situation, then all you need to achieve is to represent the alien environment in a fun way. To make this an exciting, workable encounter, you can use another system instead of the standard movement rules, which never were made for 3-D, a new mini-game that reflects the strange environment.
Having a mini-game also may help your players if they are not able to handle pure theatre of the mind well (we have the same issue): It provides clear, if different, rules how things work.
As the environment is very different from what your player characters are used to, and as you say, disorienting, with new mini-games rules the players may have fun working out in real-time how to effectively combat under these changed rules, just as their characters are trying to work out how to combat under these changed conditions.
What is a good mini game?
What worked for us was entirely getting rid of the map, and just using a concept of zones for combat, as Dresden Files uses. You define a couple of zones like "at the heart of combat", next to it "close to combat", next to that "in the distance", and after that "lost out of reach". The last one is special, you cannot pursue someone who gets there, and combatants there are not considered in the same zone, but you can get back into "in the distance" from there.
Melee attacks only happen in the same zone, as do short range (less than 100 feet) missile or spell attacks, longer range weapons can only attack into adjacent zones. Movement only can move you from one zone to the next if you spend a full round, or within a zone into melee if you spend a normal move.
To account for the special gravity (which we did not have), you might add something like a "dropped to the side" zone. If you cannot fly, make a saving throw to see if you can steer your falling movement the way you want (into melee to attack, or to get to another zone), else you move to the "dropped to the side" and then after that "lost out of reach".
There are, of course, many other ways to handle such a mini-game. The point is that it should be abstract enough to shield you from getting into distance calculations, simple enough to learn in a minute, and complex enough to allow for some tactics.