Ahhh, good old Jet Force Gemini. Took me years on and off to achieve the full ending, trackign down every little nook and cranny of it to find the hidden ship parts. The final boss wasn't amazing, but I was just so glad to have completed it that it didn't matter.
My own personal reccomendation would be Star Crusader. Playing the part of the wing leader of the Gorene (eg. Space Romans), Gold Squadron of fighter ships, you got to fly against a wide variety of aliens races, each with different cultures, backgrounds, ships and weaponry. You could manage everything about the ship you pilotted from priority of the ship's power to repair priority, and whether or not to overcharge shields or lasers. Fighting everywhere from dead space to asteroid fields, minefields, even nebulas. The characters were believable, if not always likeable, the plot was complex (at least I thought so when I was 7), and there was always the possibility that the game would go a different way each time. Failed to capture a freighter full of Zemun fgighter craft? Then we'll have to try the harder emthod of capturing live craft patrolling the edges of their border space! So fail at your peril, only to have to try something even riskier!
There's even one point where you're forced to choose either to join the alien alliance by letting an unarmed cruiser full of the alien planetary leaders blow up, or to let them die and continue to pummel the alien races into the ground, using increasingly unethetical methods like biological weaponry, sending an entire race mad, etc.
So even then, the game has replay value, as increasingly, there are other missions that you could have played. I would heartily reccomend it to anybody who can track it down.