Also get on the tor-relays@lists.torproject.org mail list.
But the sad truth is that there aren't that many hosting providers that allow Tor relays. Especially exit relays, because of abuse complaints.
Also, as you might expect, Tor relays can use lots of bandwidth. It's more common to get flat-rate bandwidth for 100 Mbps uplinks, and metered bandwidth for 1 Gbps uplinks. Digital Ocean, for example, just switched to metered bandwidth, and that has killed some relays.
However, all this could arguably change, if Tor became mainstream, as part of Firefox.
(Also check the new relay guide: https://trac.torproject.org/projects/tor/wiki/TorRelayGuide)