All major hosting companies have a sponsoring programme for startups in incubators/accelerators.
Unfortunately I cannot disclose the numbers and the companies, but they are way larger than $5k
$5k in credit for hosting probably has a marginal cost of $0.
On the other end, if you take AWS offer and start using their services, you'll probably won't leave them anytime soon, particularly if you rely on provider-specific systems (SNS for instance).
Startups get a nice discount, hosting providers get an opportunity to supply a future successful startup and very quickly win back the $5k...