In addition to what has been said, any provider that provides a (RAM-based) rescue system will likely allow you to install OpenBSD by running the OpenBSD installer in qemu, with the 'real' disks mounted as the VM's disks.

This is not a supported or convenient way to do your first OpenBSD install. Having a serial console is not necessary, but recommended (in particular, don't forget to configure <real-hw-interface>0, not the em0 that qemu is likely to offer you.) That said, I've done this before on some Hetzner serverauction (bare-metal) box, and the procedure worked fine (as one would expect.)

(Of course, you can run into hardware that OpenBSD doesn't support. Consult the man pages to find what is supported, or just try - server hardware is pretty likely to be supported.)

RootBSD does well. The latest version of OpenBSD is usually available within a week or less.

https://www.rootbsd.net/

Vultr does. Last time I looked, 6.0.

I host a few images for Linode -- including OpenBSD -- and a deploy script [1]. But my OpenBSD is 6.0, not 6.1.

[1] https://github.com/eatonphil/linode_deploy_experimental

Tilaa provides images. We run some ~40 servers with OpenBSD there.

1984.is does. I run my mailserver through them (on OpenBSD 6.0; will almost certainly be upgrading sometime this week).

https://www.tilaa.com does (FreeBSD too)

prgmr lets you run anything