Hmmm. I think you'd do well in most small cities or larger towns throughout the country. Personally, I'd be thinking about weather preferences, family access, cultural values, etc first, then do a bit of research on the rest: ie compare hydro/power rates, income taxes, health care premiums and what they cover, etc. I'm also not sure what you mean by "a paid off house"; housing costs are one of the things that varies the most widely across the country, so what constitutes a paid-off house in one region may not in another.
In BC, for instance, we have awesome weather options, low income taxes, generally excellent infrastructure and transit (compared to other regions I've experienced, anyway), some of the lowest hydro and insurance rates, cultural values that align with mine, and I have family around the province. We also have expensive housing (but less so outside the major centres), expensive health care premiums, and in the major centres, high property taxes.
In the maritimes, housing is super-cheap, but generally infrastructure is in rough shape, heating costs can be very high, and property taxes can be as well. In the north, groceries and incidentals can be way more expensive than in the south. Trade-offs.
If it were me, I'd likely look at the provincial comparisons on some of these, pick a province I liked, and then start looking at smaller centres 3-4 hours outside the major ones (so you're well out of the suburbs, but still not remote). I think you'd find awesome places in just about every province that were walkable, friendly, and cheap to live in.