Yeah, I don't remember many places on the island for organic produce, other than what you can find in the grocery stores...though I did enjoy the PEI Green Party's idea to make the whole island organic! It'd be great, but it would be a long time before that ever happened.
For organic food around Halifax, Planet Organic is probably the place to hit; they've got plenty of organic produce, and great things like tempeh, vegenaise, etc there. You can also find a place at the Saturday Farmer's market that has organic Nutritional Yeast, organic flour (several varieties), oats, beans, chickpeas, etc, all organic. Most of it is imported, though the flour and such is all ground at the Speerville flour mill, I believe. I'm not sure if there are other good places, though.