I don't know if I many any insights on that. I'd imagine the biggest challenge is not knowing what the landscape is going to be, we've seen some pretty funky cliffs and ravines, often borderline impossible. Stopping them from ending up in some stupid situation where they are plummeting off like lemmings is probably going to be as annoying as hell.
The height field maps I worked with were very predictable, most games use markers and routes for NPC's to move around known paths. With procgen, there's going to be the world 'generated' around where the player is and then there's the rest of the planet that only exists as a formula - that's got to be a nightmare for path-finding. Maybe you have a unit and you need it to move somewhere hundreds of miles in that direction, how do you map a path there? Go around a mountain range or a canyon? With any other crafted map based game, you know it's there in advance. Sure you have the 'rules' for generating that bit of the map, but simply knowing the "height" at one point isn't going to help you, it's all relative to the area around you, is there a sudden dip over that way? Is there a mountain that way? etc.
You could "look ahead" to find paths - but that's an expensive operation, pick some random point and "generate" the landscape to see what obstacles are there in advance. Sure that can be done maybe offline for all the maps that have AI units, maybe render some points selected at random until you find some "good" paths. The landscape doesn't change, so some pre-baked paths can be loaded from the server for each planet. Another possibility is to use the rule-set to generate a low-res map or the entire planet, they already do that for the zoomed out map view. So you could write some routines to generate paths from that data. Maybe you could use something more abstract like a neural net to learn how to place paths based on that information - using relative high and low points as 'avoidance' areas. That would be neat because you could factor in gravity as an input, so on some worlds the units can do the crazy canyon jump while on others they learn to stick to flat safe "low-grav friendly" routes - that's the kind of thing I'd be looking at - but then I did my AI degree at the end of the nineties
As with most thing in games the real trick is to fool the player into thinking that these things have happened rather than implementing it all in advance (imagine an online pet that loads into memory when you log on, did it do anything while you weren't playing, or did it just calculate the date since you weren't there and present the world as if it had been there all along? The later is way less expensive to implement) I'd imagine the trick is to fool the player into believing the units are moving between two viable locations. They will probably spawn in within an instance, but how far can the player follow their tracks? You might have to render the 'track' path back to a viable origin. What if the player follows the units themselves, they can't just go off randomly until they get stuck somewhere. Then there is the player interaction behaviour to think about, what happens when they are attacked - maybe that's not going to be massively different from what happens with the existing NPC ship combat but coupled with some of the above challenges.