Figured it out today thanks to all the other information here.

Settings -> Wireless & Networks -> Mobile Networks -> Acces Point Names

Create a new one for each:

Internet

Name: Fido Internet
APN: internet.fido.ca
Proxy: 205.151.11.11
Username: fido
Password: fido
MCC: 302
MCN: 370

MMS

Name: Fido MMS
APN: mms.fido.ca
MMSC: http://mms.fido.ca
MMS Proxy: 205.151.11.13
MMS Port: 8080 (still needs to be confirmed, I didn't want to test too much without unlimited MMS)
Username: fido
Password: fido
MCC: 302
MCN: 370
APN Type: mms


So far it works!