I for one really like the idea of it being in New York as mentioned in an earlier post, with the character being an immigrant, with a big gang structure with lots of little factions that can grow significantly with your help, rather than 2 superpowers. There would be ALOT of replay value potential there. each gang faction would be completly different in terms of ideals/beliefs, quests and characters and you could only choose to help 1 beyond the basic first tier of quests they have available.
Each faction would have its only storyline and unique ending. The player needs to join one of the factions (or possibly start his own) to progress get access to new tech etc and ultimatly unite the city under that gang. Once you join a faction you cant really interact with the others because you'll be seen as an enemy.
OR I would really like a deep south setting, with deep seated racisim, not against black people, but against mutants and ghouls etc