I think in the regular AGOT map, lannister has a strong advantage in 4 players and tyrell has a decent disadvantage in 5 players. My groups uses small houserules to shore those up.
In ASOS, we think lannister is a bit weaker than the others.
While yes AGOT is a diplomatic game, diplomacy is always easier when you carry a big stick.