That doesn't really have much to do with the Greyjoy-Lannister problem. Baratheon in a 4-5 player game is a different matter all together. Baratheon have the advantage of being able to capture the south without any resistance.
As far as anyone knows, there is no was to solve the Greyjoy-Lannister problem without changing the board or how Lannister starts. The way I've dealt with it is I always have Greyjoy played by a very fair and seafaring person who doesn't like smashing Lannister as they are too easy. I always play as Lannister and I manage to win later on when I'm secretly gaining strength without him knowing.