It appears that this is a feature of Terminal.app, and unrelated to the browser in any way. And as suggested, iTerm doesn't display this warning when it's started with a command to open an ssh: URL, so setting iTerm to be your default ssh: URL handler appears to be the way to go.
I just verified that by changing Firefox's default application for handling ssh: URLs to iTerm, I don't get this warning dialog. (I did this using the Preferences/Applications/ssh entry, choosing iTerm as my default preferred handler.)
Using RCDefaultApp (http://www.rubicode.com/Software/RCDefaultApp/), I was able to change the system-wide default for handling SSH URLs. (Once the preference pane is installed, go to the "URLs" tab of the pane, scroll down to "ssh", and choose iTerm from the pulldown list of applications.) Once this was done, Safari also used iTerm, and I didn't get the warning dialog.
As Randal Schwartz said in the comment, though, this is a true feature of Terminal.app warning you of the possibility of leaking information (your username) to a host out of your control. I agree that it's a bit draconian, but it's important to understand that by switching to iTerm, you give up this feature...
known_hosts
file.