Space for maps and stuff shouldn't be too much of a problem, depending on how big your maps are. Think about it...The entirety of Firered, including all the code that controls things like displaying images, making the player move, and all that, is all contained in less than half the possible space. You could fit an entire copy of the game in the free space, and you'd STILL have a couple thousand bytes to spare. That being said, if you did do that, you'd be able to have doubles of the 18 cities of Kanto/Sevii islands...basically, you'd have 36 cities. Since roughly half the coded area is ASM-related stuff, you'd have enough space for maybe 50 cities, if you budget your space correctly. You'd also be hard-pressed for scripting space, if you ended up doing 50 cities, although you can always expand to 32 MBs, giving you ample space for both more cities and more scripts.
However, you'll need to do some work. Firered only has 109 possible place names...and while that seems like alot at face value, that's really only enough for two regions and a baby region (Believe me, I know...I'm completely out of names, and I've got two regions and a baby region). You'll need to expand the possible names, which is documented somewhere around here (I believe in the Research and Development thread).
