Hey toemaytoe, I was exactly in the same situation as you. City Fido plan and blackberry envy because fido did not offer the service. Then in January, I was so fed up with my crap Moto Razr that I bought an unlocked Blackberry Pearl. Then to my amazement about 2 weeks ago I noticed Fido was all of a sudden offering Blackberry Connect Data plans although they say that they only guarantee it will work with the Nokia E62 that that sell.
I told them it would be absurd for it not to work with a native Blackberry phone and they said to try it but they couldn't guarantee it. So I registered for a data plan, thinking that if it didn't work, so what? I would just cancel it the next day and get charged 1 day out of the month for the plan. No big deal.
I went to their blackberry signup page and entered my phone's IMEI and PIN and email accounts I use and bingo, within 5 minutes, my phone was online and capable of receiving my regular pop emails etc...
Works like a charm although because it is not a Blackberry Enterprise Server they have but rather Blackberry Internet server, my email comes in between 5 and 15 minutes after it is really sent. Better than nothing I guess!