I don't think it's a good idea to simply ask if you should keep the original tiles or rework them without first showing us some examples of what they might look like.
If you can pull it off, new tiles might be great. If you can't, then don't use them. The colors for the original are pretty vibrant; maybe it would serve you better if they weren't?
As for the maps... That's a tricky one. I would personally like to see something new. But your premise doesn't really lend itself well to new maps if it's meant to be set in the same world/time as the original FireRed.
One option, although it's a pretty... Out there idea... Would be if you took the maps, rotated the layout 180 degrees, and changed the literal point of view so that you saw behind everything the player normally sees in FireRed. It'd be difficult to make something like that work because doors are generally designed to face the player. Doing this would make it so that they are hidden 'behind' the building in your version of the map.
But the reason I'm putting this out there is because it could allow you to really play with the more covert side of being in an evil team. You could have Team Rocket Members hiding out behind buildings or trees. It could also allow you to justify why some areas your player character might explore aren't in the original games. The player character from FireRed litteraly doesn't see what your character does. Maybe your character would have different tunnels to explore in Mt Moon that are on the other side of the cliffs that normally we don't see.
I hope I articulated that idea well enough. Since it is kind of out there it's also harder to explain it ^^;.
