Currently ZaReason offers a good selection of GPU hosts:
In my experience, ZaReason will install both Ubuntu 16.04 and CUDA v8.0 before they ship the host to you.
During my last order-entry experience with ZaReason, I used a customer notes section at the end of the order form to describe what software I wanted them to install.
Also I verified via e-mail: email@example.com
Also you can call them and maybe visit their HQ in Berkeley: