Re:4 or 5 players, which is better?
The Jakster (#40654),
I've played the game with 3 and 4 players, and one 5-player game (same problem as you it seems). Both 4- and 5-player games are balanced when the players recognize the relative strengths of the houses. That is, Lannister won all of our early 4-player games unless he was checked, and when he was, Baratheon almost always won. I believe (from my small sample) that the 5-player game swings this the other way: Greyjoy adds a lot of competition for the resources around Lannister, which gives Baratheon ultimately the stronger position.
Once you get a feel for the game, though, these issues iron out, because people intuitively know who to keep an eye on (and when). To that end, I suggest getting 4 together because, while I'd prefer 5, you'll probably get to play more often!
I'm curious to hear what other people have to say, because since we're always playing with the same people we can never tell if we're Playing It Wrong.