If European providers are ok, have a look at https://www.hetzner.de/ot/hosting/produktmatrix/rootserver or https://www.online.net/en/dedicated-server/dedicated-server-... the former having no ddos protection, so not suitable for anything internet-facing, really. OVH has different offerings for different CPU ranges, and also in Canada I believe: https://kimsufi.ca are the cheapest, https://soyoustart.com a bit more powerful and from https://ovh.com even more.

I've used them all without issues, but service can be really slow / even a hassle to deal with.

Give https://www.packet.net/ a try. They are relatively new (about 2 years old), but are solid and having very nice APIs.

I suggest Google Compute Engine https://cloud.google.com/compute/

I suggest http://www.hivelocity.net. They are awesome!! They only do colo or dedicated servers.