[Eagle of Fire]

My main problem with your description is that you are stating around 1996 and 1997, but your graphic description match a game made for the late '80's or early '90s.

Frontier: Elite 2 would of course be my first guess... It was made in 1993 and it used graphics similar to what you described. You specifically said it wasn't though, so...

There is a whole serie of game very similar to Elite which was named X. I think the first game of this serie was X: Beyond the Frontier. But judging by your graphical description and the date it shipped (2000), it cannot be this game either.

Could you describe a little more the gameplay of the game? More details is going to help a lot here.

Edit: I looked around on this site and realized that even very early '90s games had staggering graphics in comparison to what you are describing. Either you played a very old game back then or something is wrong with your description.