I really looked forward to Starfleet Academy but I was so disappointed with the gameplay. It plays more like TIE Fighter than a starship sim. Interplay should have done better. For some reason they had major problems completing the project. The videos are great though.
Klingon Academy is actually the same game engine with some improvements. It plays a bit better and the "ginsu" damage system is very entertaining. Some of the space phenomena are very cool. There's a black hole accretion disc that is amazing. I saw an enemy try to warp through it and fly apart!
By the way, Star Trek Klingon and Borg can be found on YouTube in walkthrough form. Good stuff. They're like watching lost episodes, especially since they use many secondary actors seen on TNG.