On the “may” and the “shall,” one of the big differences is in the estimates. In the estimates, you have different votes: you have budget spending and legislative spending.
If you put “shall”, that amount would be legislative spending and not budget spending, meaning that Parliament would not have to approve that spending every year, like the employment insurance benefits. It would go through without Parliament's approval. Whereas if it's “may,” Parliament has to approve the spending and the budget every year for that program. That's the main difference for this.