I would proceed as follows: For the release, apply the attached patch.
This should give initial and subsequent frames the same size and thus
resolve most issues you raised in this thread and also fix bug 14795.
For Lucid/Motif/Windows the toolbar would remain part of the text area,
hence the number of lines available for editing would be less than
specified.  I see no way to provide a safe fix for this without
sufficient testing.  We could increase the number of DEFAULT_ROWS for
these builds though, so the default frames would retain their prior
sizes.

After the release I would try to change the behavior such that when a
frame is created, the toolbar is not counted in the text height on these
builds.  Hence `default-frame-alist' would be interpreted as for the
GTK build.  Subsequent changes (adding/removing/wrapping) of the toolbar
would not change the size of the frame but that of its text area, so in
this case the behavior would differ from GTK but still be different from
the prior behavior.

I soon intend to implement horizontal scrollbars anyway so the necessary
changes would mainly amount to something like defining:

#define FRAME_TEXT_LINES_TO_PIXEL_HEIGHT(f, lines) \
   ((lines) * FRAME_LINE_HEIGHT (f)		   \
    + FRAME_TOOL_BAR_HEIGHT (f)			   \
    + FRAME_SCROLL_BAR_AREA_HEIGHT (f)		   \
    + 2 * FRAME_INTERNAL_BORDER_WIDTH (f))

WDYT?

martin