Also, I would recommend contacting WWFan and asking him for his Tile Split program, which can automatically tile the images into 16x16 with 1 pixel horizontal and vertical separation like you would want. It won't work for most of the large maps like the ones on that site (it gave me an error when I tried to tile the entire overworld) but it should work for the smaller rooms and such.
He also has a program called Tile Eraser which will not only tile the images, it will look for duplicate tiles and delete them, leaving you with an optimized tileset of whatever you put in.
They're really quite amazing, and I'm sad that he hasn't reposted them (yet).