I'm fine with the plan and the map (i.e. no need to re-generate it). To me, a maze map is a bit hokey and favors the human due to minimal sharing of cultural borders, choke points everywhere, not having to fight wars along a long cultural border, etc... I guess it could prove quite challenging too because the "easy" thing to do would be to just build work boats and no navy while the AI will build navies which could cause trouble. In any event, this is the map type chosen so 3 or 4-tile wide maze is fine with me.
To state the obvious, try to fully scout the water on both sides of the land (i.e. zig-zag from coast to coast while exploring) while you go. Who knows if/when that warrior will ever come back to the starting area and it would be ideal to know the seafood situation for future city locations. Even if it turns out to slow down forward progress with the exploration, it will eliminate the need to either come back or to send another unit later to check things out.
As I said earlier, every city we own is likely to be coastal, so the GLH should be on our minds as we move forward. I'm not sure if we should even worry about any of the other early wonders at all. Who knows, maybe the GLH will slow us down too much and we could get steamrolled if we neglect our army.