Is house Baratheon meant to be able to expand this quickly?
This is a "well known problem". I'd suggest to check out the variants mentioned in this post and BGG.

We prefer the "Rumble in the South" alternative:


  In this variant, Stark and Greyjoy are unplayable and their lands are impassable. The impassable regions thus include: Bay of Ice, Flint's Finger, Ironman's Bay, Seagard, The Mountains of the Moon and The Narrow Sea. This variant is excellent at creating a true 4-way battle with shifting alliances! However I tend to make the win condition only 6 castles instead of 7 to speed up the game.




Using the above Lannister tends to be overpowered because of these things:


They don't have the Greyjoys at their backs all game long.
Stoney Sept is a strategic position by the capability of giving support to six other territories.
Stoney Sept has six barrels in its neighborhood and Lannisters almost always capture Blackwater because of it and end with a level six supply.
The Tyrells can't contain the Lannister ships at all (all the ships are going against them and Lannisters almost always have a larger army (because of the supply value).
Their strongholds are far from the line of battle.


We have two alternatives to refine this, I prefer the first one:


Stoney Sept and Blackwater is separated (like having a river): no support, no march, no raid
Weaken (or even ommit) Riverrun: changing it to a castle and removing the barrel


We also tried weakening Blackwater (removing barrels), but it was a failed attempt... it lowered the motivation of others to fight for it...



In the other hand, Baratheon gets weak as hell (because of the lack barrels... they weren't able to capture Blackwater in the games we played), if the cards doesn't come in a really good order...
So we decided to keep the area called "The Mountains of the Moon".