Under CrossOver Games 7.1.1 and 8.0.0 (for Mac, and presumably Linux also) this game will install and run with no problems. (Performance was slower under the 7.2.x Crossover releases, so they've best avoided.) There are no-CD patches available if you look for them, but these are not strictly necessary.
The game itself has it's share of bugs... Many of them were resolved in the version 1.02 patch, the final official patch, that is available from various sources and will happily install under CrossOver - just be sure to run it in the same bottle as you have installed the game. That particular patch introduced a new bug whereby the opening video no longer plays.
Mouse movement can be a bit laggy, and the game can slow down over time since it has a few memory leaks, but these are not Wine problems since it was like that under Windows. The solution to this, as on Windows, is to quit and then restart the game.
There is a fairly active modding community for Star Trek: Birth of the Federation, mostly focussed
here. Most mods seem to be compatible with Wine, however you should note that some may edit the "stbof.ini" file adjusting the line reading "3D=SOFTWARE" to "3D=3DFX". This attempts to get the game to use accelerated 3D graphics, which is
not supported in Wine. You will need to change this line back to "3D=SOFTWARE" to get BoTF to run again after installing such a mod. An example of this is the popular Ultimate Dominion Mod III.
