Okay, scratch Puzzle Quest: Galactrix off the list of possible space exploration games. Not much exploration, just a pile of sidequests, and very very little worldbuilding of note, and no dialogue branches at all. Plus the writing is a lot like AdventureQuest's. (That was an insult.)
I'm not sad I bought it, but just for the sake of review: The puzzles feel like I'm playing Solitaire. Some people like Solitaire, it's kind of relaxing. But in Solitaire, good skill and strategy often loses out to blind luck. Yes, you can get good at PQ:G, but when your opponent clears some tiles, and three brand new mines slide onto the screen and instantly clear themselves in a chain reaction that kills you, it kind of gives you a WTF. You get big bonuses for long chains, but there's no way at all to plan out chains past the second or third step because after that it's just new tiles sliding onto the screen--the big bonuses all come from random factors totally out of your control.
Oh yeah, and the combat AI is not so hot. I mean it's decent as a single player game, sure--so is Zelda, and you can't say that has AI exactly. But the AI is good at finding the most profitable move on the board, chain-wise, in a way that no human player ever would be...while often being quite ignorant about the board state it leaves you, and even making totally illogical moves sometimes. (Why hit me with 3-damage mines when you could shoot me for 20 instead? Why use weak guns when you could save up for your 'halve enemy hull hit points' one instead?)
Meh, if you liked EVNova but found it to be too thinky, and if you like puzzle games, you'll probably like it anyway. But Starflight this is not.