First suggestion is to make sure that you're not trying to run these via GOG Galaxy. I'm not against GOG Galaxy in general, but it does add another layer of crap that Wine needs to deal with, and basically just gives you another breaking point. Grab the installer for the game itself from GOG and go that route. You probably already know this, but I have to mention it just in case.
Second, watch out for games that use DOSBox. Doom I and Doom II should be DOSBox games. If you try to run DOSBox through Wine, you're gonna have a bad time. /Southpark What you can do is use the GOG installer to get those games on your hard drive, and then install DOSBox via your favorite package manager. You'll need to do some configuration of your own with DOSBox, but it's not a horrible endeavor. I have half of a blog post written up on how to do this exact thing. Looks like I need to finish it.
Third, have you checked in with WineHQ? You can usually find the libraries needed for a given game, or alternatives to running the game in Wine. In the case of Jedi Outcast, someone recommends a project that's available on Github. Here's the link to WineHQ.