For the boss, why not use Twinrova? They use Fire and Ice attacks, and you can hurt the Ice one (I know their names, but I forget which one uses fire and which uses ice) with either the Hammer or the Red Candle, since, as we all know, fire melts ice. As for the fire one, I can't think of an item that has to do with water or ice. Maybe you could instead make special "magic" in the form of an Iceball or a Fireball, and you have to reflect that back at Twinrova with the Mirror Shield, like in OoT (although you slash them in Oracles). It's just a thought, but reading the "Ice/Fire Dungeon" part instantly made me think of them, since they DO use fire and ice. How ironic.
