I would love a decent first person shooter/puzzle solver star trek game on a platform like xbox or playstation. Has there ever been anything like this?
My favorites are still: The 25th Anniversary game Judgment Rites and The Kobayashi Alternative (watch out for malware - the links that say "Start Download" aren't the ones you're looking for).
Most of the best Star Trek games released are more than a decade or more old now, at least the dedicated ones with a single player campaign. As Kor mentioned in response to your question, the best examples would be Star Trek Elite Force 1 and 2 which somewhat fit the description of the type of game you are asking for (they are more action focused). There is also Star Trek Deep Space Nine the Fallen but that game is Third Person rather than first person and its action gameplay is not always as tight but it has some wonderful big levels with a lot of variety (if you can stand Unreal Tournament engine quality graphics) Most of the more puzzle solving oriented games are the mentioned Star Trek Original Series games and TNG "A Final Unity" which are old style mouse driven adventure games.
Elite Force was also released on the PlayStation 2, however I find the controls were not mapped out as well as on the PC. And for the Super Nintendo both DS9 “Crossroads Of Time” and TNG’s “Future’s Past”.
Those are all PC games, the OP was looking for console games. There aren't a lot of Trek games for the X-Box or Playstation systems. The ones I liked best would be Invasion for the PS1, and the Kelvinverse Star Trek for the last generation of systems. I haven't played Invasion since it first came out, so I don't know how it would stand up today, but at the time I liked it a lot. It's a space combat game where you are part of a squad of new single person fighters. It featured Micheal Dorn as Worf. The Kelvinverse game got horrid reviews, but I actually really enjoyed it. It's a third persone shooter where you play as Kirk or Spock as they fight off an invasion by Gorn from an alternate universe. This one features the entire Kelvinverse movies' main cast. The only other Playstation or X-Box Trek games I've played are Encounters for the PS2, which was kind of meh, and Shattered Empire, which I couldn't stand and gave up on before I finished the first level. The best Trek games are definitely for the PC.