Shattered Pixel Dungeon is pretty great if you like graphical top-down turn-based games with procedurally generated maps.

Mindustry really had me hooked for some time. The devs call it an "automation tower defense RTS". GPL-3.

SuperTuxKart

I really like Endless Sky!

It's an open source PC game, but there's an open source mod for phones on F-Droid.

Edit: i almost forgot the best part! Because the game play relies on text files in a certain format, the PC story mods work with the phone game!

Andor's Trail is a pretty good roguelike. It goes very deep. Actually, maybe a bit too deep, I have trouble keeping track of everything that is going on! But it is certainly entertaining.

Mindustry, its open source, free, has campaign and multiplayer mode, also available on pc. You can even support devs by buying steam version of the game

Breakout 71

Unciv is basically Civilization 5 with pixel graphics.

Astro Loop, roguelike shooter

https://f-droid.org/packages/com.astroloop.game

Surprisingly addictive

Simon Tatham's Puzzles is my long-time favourite and recently I got really hooked on Water Sort (though that one is a bit lackluster in custom game generation). I don't know if these meet the progression or even deep gameplay requirements, but at least they are challenging and more or less polished.

I find Feudal Tactics to be a lot of fun.

Battle for Wesnoth

Hex, turn-based, fantasy game.

Tons of campaigns.

https://f-droid.org/packages/org.wesnoth.Wesnoth/

Luanti (previously named minetest)

Block builder engine with 100s of game modes.

https://f-droid.org/packages/net.minetest.minetest/

I wonder if mobile version of Cataclysm-DDA is open-sourced, like the desktop one. It is probably the most mechanically complex zombie-survival roguelike you can find

AAAAXY