Great question! My campaigns tend to skew in one of two directions: 1) "Lovecraftian" with cosmic-horror type monsters like Mi-Go and Deep Ones; or 2) "fairy tale" with talking animals, magical beasts, and enchanted creatures.
Also there are some cool non-generic humanoid-substitutes in the AD&D Fiend Folio and Monster Manual II: Vilstraks, bullywugs, meenlocks, myconids, etc.
Last but not least, substituting NPCs (such as a competing adventuring party) instead of generic goblin/kobold/orc encounters can be a lot of fun.
I'll admit my campaign is the standard Greyhawk/Tolkeinesque style, but you bring up some interesting alternatives. My other thought was a Hyperborea style with mostly humans as opponents, with the lizardmen addded for some flavor. I actually liked the Tomb of the Lizard King module, that you can play as very dark and evil.