Take any business or building in the city, then picture it out of business and abandoned -- instant base:
- Closed zoo, weeds overgrowing the habitats
- Dusty amusement parks, hall of oddities, or empty arcades (for the Joker/Riddler types you mentioned)
- Condemned hospital or insane asylum
- The old sports stadium (preferably with a roof that opens)
- A whole mall of shops, now teeming with agents
- That skyscraper that was condemned but still hasn't been knocked down for some odd reason...
- Bowling alley, pool hall and so on
There is also the clever vehicle as base. Harder to find a moving target:
- Cargo ship, anchored on the docks or in the bay
- Subway train that roams forgotten (or even public transit) tunnels. Also works for surface train.
- Jumbo jet, that only lands to refuel on occasion
- Who doesn't want a zeppelin or flying aircraft carrier platform?
For a big, big base that was right under the heroes' noses, I had
Dr Null set up shop in an old geothermal plant built beneath the city decades ago and then abandoned and forgotten when it didn't pan out. Lots of prebuilt chambers, a supply of power, and he had easy access to the utility tunnels beneath the streets. Plus once it was discovered, the heroes had that satisfying "ahhhh, that's how he did it" feeling, since the base made sense in the game world.
[EDIT: Kudos to you Morgan -- we cross posted. Great minds think alike]