Terminal uses /usr/bin/login to launch new shells, by default this prints out the last login time and the contents of /etc/motd. To look up the last login time login searches through the ASL (Apple System Log) database in /var/log/asl/. These log files can be very heavily fragmented and it's this file fragmentation that causes the delay when opening a new window or tab.

The Solution(s):

There are a few ways to deal with this, and depending on your version of OSX not all of them will work. I'll start with what works for me on Mavericks, and then list some alternatives from least to most intrusive to your system.

Solution #1

/usr/bin/loginshould respect the existence of .hushlogin in your homedirectory which cause a quiet login, skipping the need to search for the last login time.

cd     # get back to your homedirectory  
touch .hushlogin  

Solution #2

In Terminal's preferences under "Startup" you can change "Shells open with:" to "Command (complete path)". Try prepending a -q to the path for your shell.

-q /bin/bash

Solution #3

If you try and use a "custom shell" login will use -q by default. Becoming root, creating a symlink to your shell and then using that as the "Command" to open shells with on the "Startup page" will trigger this behavior.

sudo ln -s /bin/bash /usr/bin/bash  
# then set your "Command (complete path) to:

One issue you will encounter if make change 2 or 3 is that Terminal will ask you to confirm that you want to close each tab, even if it's just sitting at a waiting prompt. To fix this go to Terminal's preferences and under "Settings" select the "Shell" tab. At the bottom add your shell to the list of commands that Terminal will close a tab without warning, e.g. bash

Observe the problem/Verify the fix:

Run the following before and after any of the above fixes and you should see that it no longer searches through the ASL.

sudo opensnoop | grep login  

If you did fix 2 or 3, you can "Inspect Tab" with a Control Click on the tab. The login command should have the -q option.