A few things.
1.) I want a ship. I was always fascinated by games like Privateer and Elite, but I could never get into the primary gameplay of ferrying trade goods around.
..snip..
2.) I want the kind of game where open-ended "puzzles" just arise from gameplay.
..snip..
3.) platformers with tight controls and satisfying combat?
Since you led with Privateer / Elite, I'll start with the X franchise (Look at the latest X3 game, I guess. I hear 4 isnt all that) in which you can but do not need to trade. Also, Evochron Mercenaries is supposed to be good. detailed ship combat, not dumbed down. Trade if you want to, but dont have to.
Bringing it to more of a top-down sort of feel and wrapping in item 3, I'm eager to see what Starpoint Gemini 2 looks like. It is available on early access now, and might scratch this itch for you.
I have a vague feeling like I've seen several games with this sort of top-down or from-behind view where you could do different kinds of missions -- fight, trade, salvage, mine, pirate, etc... maybe one of them was Russian with bad voice acting? cant find it now on a casual search, but there are several of these sorts of things out there.
On the "multiple solution" front, the only thing that comes to mind for me are ship building games like Captain Forever, Kinetic Void, and some other more blockey one that I cant remember the name of. It looked cool, in the demo you had to place specific blocks for armor, power conduits, turrets, shield generators, docking ports, etc.
in the X series you were supposed to be able to solve problems economically instead of militarily. by placing or destroying mining stations, you were supposed to be able to make it so that an empire had to follow some path to get a resource they need, and that path might lead them to war with a neighbor. I'm not sure how that panned out, I don't think it worked in the end.