We don't need a huge amount of space, probably less than 400mb will work great. The problem we had with our previous host is that our site used a a ton of bandwidth (just under 30 g a month) and also times when we had 30-40 members on the vbulletin at one time it used up more than our share of the MySQL resources and we would get bumped off.
Once we could get our site up and running again for about a month or two, I am pretty confident we can can raise the money (through merchandise sales, sponsors/advertisers, and member contributions) to move to a dedicated server. What we are looking for now is a host who can at least give us a decent deal and STABLE hosting solution on a temporary shared server and then when we can afford it, upgrade us to a dedicated server.