A lot of people have been noting that Baratheon has too easy a time rolling through the south in 4 player games and suggested replacing house Greyjoy with Tyrell. I'd love to start a discussion with anyone else who has tried this.
I've tried it and think it makes the game a little more balanced.
Lanister has some immediate relief in that they are no longer surrounded on every side, which seems to be a major issue for them when Greyjoy is in play. The presence of Tyrell means that the Lanisters cannot simply expand to the south for an easy win, so they come off only a little bit ahead. I still suggest placing the 3-player Greyjoy neutral token on Pyke so that it cannot be captured.
Meanwhile Baratheon has to contend with Tyrell and is much harder pressed for fortresses. When we played, the two houses conquered most of the southern continent and the result was about 5/6 strongholds for each of them from turn to turn (depending on exhchanges with the other players).
Stark gets a clear advantage if no one puts pressure on them, but Lannisters will probably want to press North anyways, and Baratheon has the option for naval assault in a pinch, so it seems to work out.