If I understand correctly, a Canadian college diploma is for a 3-year education, while a degree is for 4-years. Japan doesn't count the number of years that you needed to get your degree. The visa regs only say "must have graduated from university or acquired an education equivalent thereto".
Application for Certificate of Eligibility
Big deal. You are both qualified to teach here, and that is regardless of what your majors were (unfortunately).
College, university, Japan doesn't know the difference. You graduated, and that's what counts. You may have to dance a little around the description of a diploma vs. degree, but try to avoid doing that. Point out you
graduated from a college, and see if that's sufficient. Get on the
ESL Cafe discussion group and see what other Canadians have done.
Canadians also have the option of getting a working holiday visa (degree or no degree, diploma or no diploma) that allows part-time or full-time work here. Technically, you are not supposed to use it for long-term work, just a few months at a time, but that rule is often bent. You pay 20% tax, which is different, and you have to renew the WHV after 6 months for a second (and final) 6-month period, and you can use the WHV only once in your life, but you don't need an employer to sponsor you for it, unlike a regular work visa.