Unfortunately, the game does get easier as it progresses. Josephine can be difficult in the wastelands, but I found the fight disappointingly easy (though I did do all quests, explore everywhere, delayed level bonuses as late as possible, etc so was stronger than average entering the wastelands). I used a total of 3 minor restoration potions there for healing.
Kiya's
Wastelands webpage contains screenshots of the dungeons, including the paths to the Black Ring members.
I didn't find the puzzles very complex; there were usually only a couple different new directions you could explore at a time, and as you explored a couple levers would open sealed areas.
The dungeons do contain doors and openings which are blocked from view, but if you click on the other side of a wall your character will head for that spot if there is access.
BTW, with Beyond Divinity, Larian did the last act first, so if the end of development was rushed it would not hurt the end of the game. The publisher for DD set a sooner than optimal release date, so the plans for the wastelands were scaled back, and it was left almost straight hack and slash.