Asparagus can be done here. Need to get crowns in spring though - Vesey's in PEI does mail order, but you can probably pick them up at Gaze seed in St. John's as well.
Fruit: Strawberries are good. Currants are an excellent fruit crop here, maybe the most reliable. Even years we had no blueberries, lots of currants red and black. As long as moose don't eat the bushes. Mint is a good companion under gooseberries, it seems to repel the nasty little moths that eat all their leaves in some situations/years. Still looking for a moose repellent.
Dogberries make great jelly. I think the best plan for fruit is to have a diversity of stuff, some may fail but hopefully not everything in the same year.
Horseradish and sunchokes are good.
Seasoning herbs: sage, thyme, lovage... lemon balm is another one.
Alliums: Egyptian onions, perennial green onions, leeks are making a perennial patch for me here. Shallots didn't do so well, but maybe my fault, bad timing dividing them. The chives in my garden came from my grandmother originally, up in Bonavista Bay.
