How do I start gnome-terminal with a specific width/height?

man gnome-terminal reveals that this is the way:

gnome-terminal --geometry=20x20

The above will create a 20x20 window (measured in characters, see Specifying X windows' geometry in the coordinates obtained from wmctrl)

You can edit the Profile of the Gnome Terminal by going to the Global Menu, option Edit/Preferences in which you can enable the "Use custom default terminal size" and set the default columns and rows size as shown in this screenshot:

The modifications you make to your Profile will take effect the next time you open a terminal.

Gnome Terminal has changed since @Geppettvs' answer 8 years ago.

In GNOME Shell 3.36.7 you are still able to change initial size, as explained in gnome-terminal's Terminal sizes help:

If you require custom size Terminal windows, you can also set the default window size according to your requirements:

1. Press the menu button in the top-right corner of the window and select Preferences.
2. In the sidebar, select your current profile in the Profiles section.
3. Select Text.
4. Set Initial terminal size by typing the desired number of columns and rows in the corresponding input boxes. You can also click + to increase or - to decrease the size.

The Edit > Preferences menu also looks different: