In 10.5 and previous versions of the system, Terminal's remote connection dialog (go to the menu item Shell » New Remote Connection...) had a selection for Secure Shell (ssh) that defaulted to 'SSH (Automatic).' In 10.6, this has been changed to default to 'SSH Protocol 1.' None of my servers support SSH-1 (and if yours do, you should fix the security hole and disable it). [crarko adds: Here's a nice little FAQ that describes the SSH-1 and SSH-2 protocols. SSH-2 is newer and more secure.]
Also, Terminal does not remember the state when you change this pull down. Quitting Terminal or changing to another protocol and back will reset the pull down back to SSH-1. Here's a simple way to force it to keep the change.
Since there doesn't seem to be a way to save the state of the pull down, just ignore the built-in Secure Shell service entry entirely and make a new one.
Click on the + under the Service list (within the New Remote Connection... dialog box), and create a new service.
Type ssh into all three fields. If you want specific special ssh options for every ssh session (like -2 for SSH-2 only, or -4 to only use IPv4 addresses), you can add them to the command line here. See man ssh for the available options. You can pass the username for the remote machine when you go to connect to it from the dialog.
Now this new service will default to whatever you want to set it to. It won't have additional options in the pulldown protocol menu at all.
[crarko adds: I tested this, and it works as described.]

