I've been working on a NES styled game, but it won't be for the contest because it's not a remake, unrelated, but I do have some tips to share from my development.
The overworld is similar to Zelda in view, although the combat will be like Dragon Warrior.
The world is composed of 64 maps which I used an external editor to construct. Maps are created from 8x8 tiles that were made using the NES palette and the color limits, so maps have under 16 colors.
For storage purposes, and because I seem to be having issues with BMP showing the correct color, I converted them to PNG files so they're 1/10th the size.
Maps are 248x240 (NES native res).
To make things easy, I combined all the maps in full res into one image, using a grid set to 8x8 and layers in Photoshop(you can use GIMP too) I colored in 8x8 section in white as the flag for a solid area. After the collision areas have been colored I extract the area of the map and then reduce that collision map image 1/8th the size so each 8x8 cell is one pixel.
I also convert the map and collision images to 8bit colors to save on size.
In GLBasic I have a two arrays to handle map data. One handles the direction exit destination maps, the other handles the data in the collision map image. Since I been having some issues with sprite2mem, I simply read the image with getpixel to set the collision flags.
Current map ID gets stored in a 'lastmap' variable and the new map and collision data are loaded when you hit one of the direction exits, using the old image and new to create the panning like in Zelda.
Another benefit of putting all your finished, full-sized maps into one image is that you can see if everything lines up correctly, which I've found a few of my own that did not.
Hope this helps.