Oxford Dictionary indicates a public holiday and a national holiday are both defined as
A nationally recognized day when most businesses and other
institutions are closed
Whereas a legal holiday is
A public holiday established by law.
So officially legal holidays are government established holidays.
Honestly, though, in my experience (which is mostly from the US), I believe most people don't pay much attention to the varying terminology, and mostly just refer to them as holidays. If they do want to indicate an official holiday, I believe we tend to use the term federal holiday more...
A public holiday established by the federal government of a country.
The biggest distinction between a holiday/public holiday/national holiday and a legal holiday might be in instances when true holidays fall on the weekend, and then a neighboring weekday becomes the work/federal holiday. But like I said, I'm not sure general people worry about the proper terminology much, just more often just interested in anything that is a holiday!