All of those are highly debatable.
Maui is far more commonly described as a trickster folk hero (albeit one who sometimes become a demigod) than a trickster god - not all tricksters are gods! (Reynard, who was a Christian european folk hero trickster, is a blatant case in point). Hercules, likewise, while he is indeed the son of a God (and thus a demigod by Greek standards), is a mortal human, like all greek demigods tended to be. It's only at the point of his death that he is raised to Olympus as a god by Zeus - so Hercules-the-hero definitely count as mortal, not god.
Orisha are a little closer but even then seem to be more generally described as a class of spirits rather than outright gods. That's a hazy distinction, of course, but it's still a gray zone. (I would frankly have removed Oya and put in Sundiata KEita instead, then replaced one of the other male heroes with one of the gals.
With Quetzalcoatl, in comparison, there's no question about it. Quetzalcoatl is a full-on god. And I would agree that those should, in fact, be avoided (as should generally any figure deified by major contemporary religions).
As for who I would love to see: Scheherazade is the name that immediately jumps to mind - and an incredibly flavorful choice, in a game mode that's all about the stories of heroes, the hero who is legendary for telling the stories of heroes surely deserve a place. She also add another woman to the roster of heroes, and a very interesting peaceful/non-combat hero option whose charge ability would obviously be called 1001 Nights and prevent a certain number of enemy units from attacking for a turn.
I was referencing the song. 
