I know Elite Force is widely praised, but I have to pass on that one due to FPS games (especially older ones) always making me ill.
Klingon Academy could be frustrating because of bugs, but the combat was fun (if a bit clunky) and I loved the storyline. Having David Werner and Christopher Plummer reprise their roles as Gorkon and Chang -- along with Michael Dorn and George Takei doing some work in the recording booth as well -- definitely didn't hurt.
The only reason I don't have the original game still installed is because I couldn't get it to run on a newer machine/OS.
Being able to play it again would be a dream come true.