Warlord beats Troll, Troll beats Elf, Elf beats Water Sprite, and basically everything else beats Enchanted Bunny.
If you read through the winter booklet, it shows you how to use leaders with The New Era. I don't recommend getting the 51st state just for the leaders, as the game is quite great with just winter+edit:The new era.
Can I just use the leaders that came with the new era? I have no idea how to play this game yet. Should I mix in the winter expansion right away or wait?
Play both New Era and Winter immediately. Winter takes all the leaders and instant action cards and puts them on a separate board (Frozen City) rather than having them mixed into the draw deck. It makes the game a much smoother and better experience IMO. You can use a worker to take the top Leader or top Instant Action action card using Winter rather than waiting for it to randomly appear with all the other cards in the draw deck.