Re:Eastern Canada: Quebec -> Halifax -> Cabot Trail -> Bay of Fundy
Thanks for the tips. Unfortunately we left on Sept. 27, so I didn't see them until just now.
Umbada - We did hit the market I had some kind of Jamaican egg roll that was really good. Cathy (the new wife) had a Chinese chicken and rice thing that she didn't like, but I thought it was at least passable.
I did try the donair at "The King of Donair" at 2 a.m. one night. They used a tortilla instead of pita bread, but it was quite good. The sauce was definitely different that the dill sauce I'm used to -- sweeter, like you said -- but it worked well. And it was very messy.
We hit Maxwell's Plum for dinner the first night we were in Halifax because of the $7 14 oz. sirloin deal. Not the best sirloin I've ever had but for $7 it was a great deal.
The second (and last) night we were there we went to Fireside, which was a nicer restaurant with a really homey feel, down to the fireplace. I loved it. The scallops were the best I've ever had -- they tasted like steak. Even Cathy, who never eats seafood, thought they were excellent.
Like Ayersian pointed out, it requires more digging to find stuff on Canadian restaurants, so it wasn't quite the Roadfood experience we'd hoped for, but we still found some good spots.