Its not quite obvious how to change the default size of gnome-terminal from the gconf-editor menu. The terminal itself is a subset of xterm. Gnome-terminal is an xterm emulator, and it follows a termcap file for this.
On gnome based distributions (Fedora/SUSE/Debian/Ubuntu etc.) do the following:
sudo gedit /usr/share/vte/termcap/xterm
There’s a lot of stuff in this file you probably don’t want to touch, but you can change the line that describes the terminal geometry:
xterm-xfree86|xterm-new|xterm terminal emulator (XFree86):\
:co#80 specifies 80 columns, and li#24 specifies 24 lines. Change this to 100 and 30 or whatever you want.
Now all terminals should open for this default size.