Please, explain me what is going on here. IK for arms is good, but legs give me headache.
One big influence on this issue is bone roll. You can check the roll of a bone by selecting it in edit mode, pressing "N" to open the shelf and looking under "Transform." If your pole target bones (knee bones) don't have the same roll as your leg bones, it can get wonky. You can reset the roll of your bones by selecting them and pressing CTRL+N . Recalculating along the global Z axis can work well in this case.