Yea, I see where you were goin with it but Conkeldurr holds 2 stone pillars and is a mono Fighting pokemon. So the anchors could just be a sign of strength. And to be honest, another Water/Steel wouldn't be so bad, as long as there's not ANOTHER Fire/Fighting starter. I think you should just go with making the starters good, like you said. You can make the griffins become a Dragon and keep them as the Fire starter, make the sharks either Fighting, Ground, or Steel, and then replace the Grass starter line and maybe use Electric, Ghost, or even Rock would make a good secondary type. Hope that gives you a few ideas.
As for a few other things, the physical/special split is probably a good idea to improve the game. Since this is a FireRed hack, that will have to be done manually...for tiles, you're doing a good job, but I just wanted to mention that you should try to make them really pop. An exellent example is the awesome work Dante did in the Ruby hack, Pokemon Crono, if you wanna take a look. Last thing - do you plan on adding new moves and/or abilities?