Opening tab in Terminal resizes window
While this is not a full solution but more of a workaround, I still thought it's worth sharing.

Like many on this thread, I noticed that, much to my annoyance, the Terminal window changes size when I add new Tab on El Capitan (10.11.3). I'm also using Spectacle for arranging my windows from the keyboard. I thought it might be an issue with spectacle but the same happens when I quit spectacle and resize Terminal windows with touchpad. 

From what I noticed it only happens to me when when the below sequence is followed:
1. Open a new Terminal window
2. Add a new tab
3. Make the window smaller (height or width)
4. Add a new tab, and this one will change the size of the window.

Nothing happens when I make it bigger. I figured through experimentation that each and every tab in the window must be holding it's dimensions form when it was last viewed. In this particular scenario the last new tab in step 4 will change the size of the window to what it was when tab 1 was last viewed.

Now this is most important bit.
The new tabs will adjust its dimensions to the biggest tab in the window.

Workaround:
When I resize the Terminal window, I use Shift+CMD+Arrows to quickly browse through all the tab in this window. If I do that, new tabs will not affect the size of the window.

While it might be useful to some, I understand that it is not really practical, especially if you have a lot of tabs open. It is my way of dealing with this until a proper solution comes along.