I'm going more by FF1 NES rather than GBA. Also, it's been some time since I played, so I may not be accurate, I'm more going on my memory which tends to fail me.
Chaos Shrine
Masamune is nice. I never really had problems except for Chaos himself, who loved to Cure4 himself and take us down easily. This was on the GBA version though. I think I didn't have a problem with the NES version of Chaos.
Marsh Cave
Blah, Marsh cave. Despite there being a few things you can get once you have the key, I never bothered. It takes too long to get there, overabundance of poisoning enemies, and the treasures there aren't really great. Maybe not the most annoying, but certainly up there. And having to fight Ogres/Creeps for enough money to afford Silver swords, Fire2 and all that is another annoyance, because you know you have to do that for the Marsh Cave anyway.
Cave of Earth
Hall of giants is pretty good for levelling, plus Earth elementals in front of chests. Unfortunately that Steel armor costs so much. It's pretty big, and at lower levels Cocatrices/Perilisks can kill you in one hit. I didn't consider it particularly annoying, plus it was nice to finally be away from Elfland and that area.
Volcano
The fire damaging can be annoying, but other than that, I wasn't particularly annoyed with it. I dunno why.
Underwater Shrine
I sometimes get lost here. Other than that, mermaids. That's about it.
Desert Spire/Mirage tower
Sometimes get lost in here too. You get some pretty nice stuff in here. Too bad WarMech's around. 1 in 64 chance. Heh. I'm unlucky enough to pretty much always run into it.
Temple of Chaos
If you mean Temple of Fiends, it is the simplest dungeon ever. Go straight, fight Garland, hope he doesn't knock you all down. The treasure isn't really worth it in my opinion.
Ice Cavern
Between armies of undead, Sorcerors which either stun the whole party or 1 hit kills them, Cocatrices (I believe they're there, I could be wrong and maybe it's Perilisks) which 1 hit kills you, Eye which one hit kills you (Although gives great EXP), and just getting lost falling into holes makes this one my most annoying. Plus I think you need to take a canoe to get there, which makes you fight monsters that poison you.