FYI, I just discovered a VPS provider DigitalOcean, and they seem fine with people running non-exit nodes:
https://www.digitalocean.com/community/questions/tor
The cheapest plan is $5/month (256mb ram, 1 core, 20gb drive) with unlimited bandwidth. They give you New York and Amsterdam IP addresses. I haven't tried running a relay on it so I don't know how much bandwidth you can practically use, but it looks promising.