Did you guys ever do a post-mortem on how you might have solved that problem, or even how other games solved that problem?
If this was 1997, this would've been around the same time as Star Fox 64, and while that game was mostly on-rails (like Panzer Dragoon), it did have the "all range mode" maps where your movement was fully 3D. I played that game quite frequently as a child, and I don't remember ever feeling like I was having trouble hitting the enemy ships. Maybe the game had a very generous auto-target/fudge factor turned on so that the player felt like their aim was more accurate than it truly was?
Obviously we all knew of things like Star Fox 64 which is still really just a 2D game in many ways (following a fixed route), the idea was to not be on a fixed route and be free roaming.
We tried putting the player and all NPCs on a height-map - so effectively your vertical movement was based on a height map, which meant everything was vertically aligned - it was the closest it got to being decent (not sure why it didn't make it to the demo). It did allow rapid movement, less concern about targeting, and avoidance of low buildings, etc. (which allowed some of the Defender pace). However watching your bullets going up n down along a height map was weird.
But even then the free roaming nature of the levels meant that there wasn't ever an urgency to get to a place and do a thing. Each level would have targets to get to within a certain time, but then it was going away from shoot-'em up into capture-the-flag. Really it was misguided from the start.
By the time we'd tried lots of different options we'd run out of cash. I was 21 at the time, and it was pretty much my first software engineering job (I did do some educational software before that, but nothing at this level). So I wasn't perhaps as reflective then as I am now - and I left the company not long after.
If this was 1997, this would've been around the same time as Star Fox 64, and while that game was mostly on-rails (like Panzer Dragoon), it did have the "all range mode" maps where your movement was fully 3D. I played that game quite frequently as a child, and I don't remember ever feeling like I was having trouble hitting the enemy ships. Maybe the game had a very generous auto-target/fudge factor turned on so that the player felt like their aim was more accurate than it truly was?