Definitely look out for Humble Android Bundles, that’s where I get most of my games. Meanwhile, here’s a few specific recommendations - just stuff that I like, so take with a pinch of salt ;-).
Anomaly is a reverse-tower-defence (choose and upgrade an assault force and guide them past enemy turrets) that might float your boat. I think the sequel is out for Android as well. There’s a port of the linux TBS Wesnoth that can be had for a couple of quid, and if you fancy something with a bit of a horror flavour try Call of Cthulhu: Wasted Land. Great Little War Game is also not too bad if a bit simplistic.
The Spiderweb RPG Avadon is available for Android - I think it’s pretty much identical to the PC version which is what I have, but needs at least a 1280x720 screen.
Also look out for the Trese Brothers games. They fall somewhere between RPG and TBS, with the spacehulk-like Templar Assault, sort-of-elite-or-X-like-but-turnbased Star Traders, and the most RPG-like game which is Cyber Knights. All are quite deep, with a decent bit of complexity to them. Templar Assault is set in a series of levels, Star Traders and Cyber Knights are basically sandboxes. The free versions are much more than demos - they’re essentially complete games. The paid versions add in a bunch of content like extra gear, ships, additional factions etc with the proceeds going into more development - updates are frequent. The free versions are completely ad-free and require no special permissions to install. Graphics are simplistic and sometimes a bit ugly, but enough to do the job - but if you bounce off the free version there’s no harm done.
Hope this helps!