Rigging a humanoid problem: Parenting with automatic weights twists legs around
I found a solution:

BEFORE applying the armature to the mesh, I moved the leg bones so they wouldn't be completely straight and would have a slight bend in the direction the knee should move after being applied. After that, it was a matter of adjusting the pole angles.