I just found it weird, because they literally declared war 4 or 5 turns after I first encountered them. I had not met any other race at that point (other than Antarans attacking me)
If they're in a cul-de-sac, they could well do it the turn you encounter them. This is particularly true of the more aggressive races (and the Klackons aren't too far down that track).
The option for an alliance wasn't available at the time it happened, so that's why I went on the attack
You have to build up a relationship, so if you're in a hurry...
I keep bombs on some ships to weaken a planet before sending in troop transports (for when I don't have the ability to mind control them, like my Trilarian game). I think that game has been the most fulfilling, outside of not being able to travel to a lot of the map (even though I can see it from having traded or stolen maps from other races)
The missiles can soften a planet up too; they're just not as efficient at it.