Usually if I play as lannister my first move is send a message to GJ asking for an alliance. However, I've noticed that if there is an inexperienced GJ, that may not be the best option. Or if I do ally up, backstabbing within a couple rounds is ideal. I've seen so many inexperienced GJ's make bad moves in the beginning of the game-- using Balon in the first battle, putting a CP on pyke in turn 1, letting me take RR in turn 1 and moving ship out of ironman's bay and into sunset, etc...
In short, I feel like having an inexperienced GJ player narrows the GJ/lannister imbalance enough that I don't necessarily feel the need to ally up at the beginning. If i can get stark/tyrell on my side (which I usually can) I can usually get the upper hand