Use this in your Action:

File > Automate > Fit Image

That command will "Constrain Within". So, if you use the dimensions 500x500, then the bigger dimension of your target pic will be brought down to 500 and the lesser will be less than 500.

Works for me. Should work just fine for you.