Depends on what you have currently, If youre say on shared hosting, once you start seeing your website slowing down its normally a good time to upgrade (or if your host tells you they refuse to host you anymore because youre taking resources from others) Normally you'd upgrade to a VPS, depending on your computer knowledge also determines how much you'll pay, unmanaged servers come cheap, super cheap for good specs. Although if you have not so good computer knowledge you'll be better off with a managed server.
Taking the vps leap will take quite a bit of cost depending on the luxuries you want, for example, if you want cpanel (which comes with just about 90% of shared/reseller hosting now a days) that will normally cost ya $15/month extra, sometimes you can score it free on a sale or promotion.
I strongly recommend you check out
here Great area to snag good deals. I've managed to get some friends 40gb disk / 350gb bandwidth on a premium host for only $3/month which they were paying about $6/month for 5gb/100gb on their old host. The new one was also a reseller package unlike their old one being a standard shared host.