edit: Getting "Bandwidth or Storage Limit Exceeded" when attempting to download from the Solarus packagecloud.io. Sadface.
Some of the most beautiful 2D graphics I've ever seen in a setting absolutely soaked with atmosphere and detail, really nice responsive controls, and hard, rewarding gameplay.
Can personally confirm that it works pretty well with WINE on Linux (even got my xbox360 controller to work using xboxdrv in xpad mode, shockingly) -- just the intro movies won't play, but other than that it works great.
(On your specific video problem: Trails uses DirectShow to play the videos so make sure your Wine setup can play them)
To the GP: Recettear has combat like the older Zelda games (with a simplistic shop management sim tacked on. I think the Ys series also has combat somewhat like Zelda. Perhaps Diablo clones might interest you. Which bit of Zelda are you looking for?
[1] http://moonlighterthegame.com/ [2] https://www.youtube.com/watch?v=ytQNG5t8wCs