I did not see any options in FC4 to save Gnome Terminal Windows Size and I was getting annoyed with Terminal size resetting everytime I close the window. So, I did a little research but did not find much about it. Then I asked about it in fedora-list and got 2 answers:
1) Create a shortcut to gnome-terminal --geometry=80x10
2) Adil, I had the same problem... switched to 'konsole' and am very pleased.
There are also a few bugs in konsole, but it is more flexible, and
offers more control than the gnomne terminal. It may not be on your
desktop. Type 'konsole' in the "Run Applications".
I tried both and both works fine!