You need regular hosting, can be windows cand be linux, it doesn't really matter. It should do the job.

I'd be a bit worried about something being wrong on your end, given that you had the same issue with two different hosts.