Here are a couple Android games that I consider to have reasonable permissions considering the included features:
Rusted Warfare: (Red Alert style RTS) - Internet (it is multiplayer capable), Access Wifi State, Write/Read External storage, and Check License
Space RPG 3: - Check License
Other games on my wish list that appear to have decent permissions: Age of Civilizations: - Appears to ask for full network permissions
1941: World War Strategy - Asks for Identity, USB storage, and License check - Privacy policy indicates that the developer does not obtain any information through its app, however it does use Google Play Services for online play (google's privacy policy applies).
Atlantic Fleet: (Developers of Cold Waters) - Could not find a privacy policy - Appears to ask for full network access and network connections.
All of the games I have listed are paid games. Cheers!