There's a small strategy game called ‘Antiyoy’, with simplistic mechanics, which works for short-ish games: you can do a stint while waiting in queue or such. Iirc ‘Antiyoy Classic’ is entirely offline, while the regular one has an online mode. Both have no ads and near zero permissions, unless something changed since I last played.

You can try ‘Diplicity’ for an online strategy a-la ‘Risk’ where you bargain and do alliances with other players, until one of you wins the whole thing. There's no randomness. It's an implementation of the board game ‘Diplomacy’.

‘Hocus’ is a nice spatial puzzle with impossible geometry. Iirc it requires payment for additional levels, but has no ads.

The app ‘Fabularium’ runs text adventures, i.e. games where you type your actions and read the description of what happens. There are a myriad of such adventure games, many with novel mechanics. You'll need to download the games themselves separately, mainly from IFDb.org. ‘Fabularium’ isn't the only app that runs text adventures, but I like it and it supports more formats than some other apps do.