Nova Scotia rather than Newfoundland - have people read "No Great Mischief" by Alistair MacLeod. A haunting, heartbreaking book, but quite wonderful.
Equally haunting and wonderful: "Le Testament Francais" by Andrei Makine.
And finally, I want to put in a good word for Iris Murdoch. I think my favourite is "The Black Prince" - one of those books you think you understand until you realise eventually that you had understood nothing.