In the end I just settled with the logic based ones like minesweeper and sudoku. F-droid has a good version each (and more than one maybe).

PlanetCon is a decent strategy game on its basic settings. I haven't customised it but have had a fair amount of fun in it. But it is nothing perfect, do not expect too much out of it. If you learn how to not attract the ire of all AI opponents simultaneously though, you can have short bursts of decent strategy enjoyment.