Try Gossamer Threads (https://gt.net/). What are your reasons for not using Linode or DIgitalOcean anyway -- do you work for a university library or other public institution?

Starting at $250 a month for a VPS? I don't even want to know why...

Because its fully managed. Can't say for sure if its worth it, but I have heard good things about them.

No, I don't need this to comply with PIPEDA, but for a couple of my projects it would be nice to be hosted within the country.

I've used http://www.netelligent.ca/ VPS in the past. They have a cloud version now but I've never tried it.

This company was a client where I used to work and seemed very knowledgable and friendly: http://www.cartika.com Not really the same as DigitalOcean but they offer VPS hosting with data centers in Canada(and US) and they are based in Toronto(or where 2 years ago, they grew quite big since then)

OVH has a big datacenter outside Montreal.

http://www.ovh.com/ca/en/vps/

There's CloudA (https://www.clouda.ca/) that is similar to DigitalOcean.

Thanks for the suggestion, but CloudA is what I mean by "amateurish". Their website is extremely confusing (compare to https://www.digitalocean.com/ or https://www.linode.com/). They even use StackOverflow logo as an icon for their "Fast Spin Up Time" feature. All this does not inspire confidence.

Ok. Digital Ocean itself is supposed to come to Canada sometime this year if you can wait.

http://cloudatcost.com have vps starting at 35$ one time (yes, one time really)