As an after-trip report, I went to a Fido kiosk (mall at McGill station, to be precise) and bought a Fido SIM card for $10, put $20 on the pay-as-you-go account. Calls worked just fine after registering on the Fido network:
Settings -> Wireless & Networks -> Mobile networks -> Network Operators -> Fido
For a N1 data, you need to buy a $3/20MB-day plan. When you open your browser and try to do go somewhere, you get redirected to a Fido site that asks you to authorize the $3. Clicking through does that. However, no additional data worked.
After much fiddling, the guy at the kiosk was able to get my 2G data working.
He said we went to back to the network operators screen:
Settings -> Wireless & Networks -> Mobile networks -> Network Operators -> Fido
A press-hold on the Fido selection got a user/pass entry screen (fido/fido).
This worked, though
he did it, not me. When re-authorizing the next day, data didn't work again.
I didn't have the time to go back to the kiosk and ask him to repeat the process. Sorry future-me.
(Oh, and yes, I did try the above process myself.)