The weird trade things between the provinces are more to do with special exceptions and regulations around alcohol, trades regulation, etc. than the kind of tariff-oriented things people are talking usually with "free trade". They're a product of the fact that Canada, like the US, is a highly federal system and the provinces have strong powers. In some cases, stronger than in the US system (and in other cases, not)
In any case, we already have a free trade agreement with the EU. In some respects for some products its better than what we have with the US.