There are enumerable ways to solve this, not sure which is best. Attached is a small(2 line) patch that has fs2_open change the working directory to whatever the env. variable FS2_DATA_DIR is pointing to.
Yes, have the caller change directory to the game data directory before calling the binary. This is what wxLauncher does on linux.
That being said, if we go this route, we should have FSO log that is it is changing dirs (and the directory that it is changing to) so that the support ninjas can tell what is going on. Also, IIRC (I don't have the code in front of me) logging would have already started, which means that the log file is being written to the old working directory.