What if we used "Air" units as ships instead of Naval units? Or perhaps a hybrid of both?
Land and air could cross land, air and naval could cross sea.
Land = Standard Units (stormies, etc)
Naval = Large, non-atmospheric vessels (Death Star, Capital Ships, etc)
Air = Smaller, atmosphere-capable vessels (X-wing, Y-wing, Tie Fighter, etc)
Most of the code is in place already for allowing transportation using this mechanism. Simply transform space into naval and all types of units should be able to somehow cross from land to land (though Naval will never be able to reach inland, just like in-game). This works out quite well in numerous contexts, from a 2-Dimensional point of view. If we were to go into a third dimension it WOULD require code work, but is definitely possible.
Alternatively, we code in a new domain type, Space. Solves all the issues just puts some work into its implementation.