What you’re describing sounds like an issue with either A-GPS (a mechanism by which sat navs can receive initial data over a cellphone connection, without which the initial location search can last up to 10 minutes, but afterwards it will be as smooth as always) or approximate location (a mechanism in which Google uses a huge database of cell tower and Wi-Fi data to quickly get your approximate position).
I would suggest checking the permissions on the OSMAnd app – maybe it’s lacking something that Google Maps has?
These days “games I can play on Linux” is, like, almost every game released on Steam. Install Steam via your package manager or Flatpak, set up your account, and the vast majority of both native and Steam Play-based games will install and run very well. (The only thing worth noting is that while Windows and Mac versions of games are indicated by Windows and Apple logos, Linux native games are indicated by the Steam logo for SteamOS.)
In addition to that, there are free and open-source games that may be available for installation straight from your package manager (or Flatpak). Here are some:
OpenTTD is a clone of Chris Sawyer’s Transport Tycoon Deluxe series, but with massive improvements to both UI and game logic. Run a transportation company, move people and cargo from one place to another, make money, expand, compete against AI or human opponents in online multiplayer.
Xonotic is an original Quake/UT-style FPS. I don’t play it much, but I have friends who really enjoy it.
“The Battle for Wesnoth” is a turn-based strategy game with gameplay reminiscent of console/handheld titles like Advance Wars, but redesigned to better suit PC gameplay. Has both singleplayer missions and online multiplayer.