Part II has "traditional" dungeons, but they're still insanely tough. Most dungeons feature pitfalls and/or transporters that take you to various places, thus making them extremely tough to map. Just look at this shiz.
Now part III is weird. Most of the dungeons are easier to navigate - they're either castles or "glass" rooms with a bunch of impassable holes you must navigate around.
I recommend all the Phantasy Star games, but seriously, use maps.
![Laughing :lol:](./images/smilies/icon_lol.gif)